Stacks as Data Structure
Stacks are simple data structures that utilize Last-In-First-Out operations. They are commonly used for tasks like expression evaluation, syntax parsing, and checking balanced parentheses. This structure works by adding elements to the top and removing them from the same position. Explore how stacks are employed in various operations and learn about postfix notation in arithmetic expressions.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
cosc 2030 Stacks
Stacks Stacks are a simple data structure that uses LIFO (Last In First Out) operations. A new element is added to the "top" An element can only be removed from the "top" as well. For this data structure we don't have random access and unlike liked lists, we don't have access to the end of the list either.
Stacks Operations Push examples Expression Evaluation Infix, Prefix, and Postfix notation Expression Conversion infix to postfix Syntax Parsing most compilers use a stack. Parenthesis checking, are the parentheses balanced. String Reversal Function calls function calls all use a stack. Java assembly code is all stack based language. add new item to top of stack Pop remove top item from stack Peek return value of top item in stack "zero" value if empty. Empty/isEmpty T/F if stack is empty. size/getSize return the size of the stack.
Simple Balanced Parentheses looking at the following we can use a stack to check if we have enough Parentheses. Balanced is for each ( there will be a ) examples (()()()()) (()()(() (()())()) Algorithm using a stack parse the string from left to right. For a ( push it onto the stack for a ) pop it off the stack If we pop on an empty stack then error, unbalanced ( if the stack is not empty when we reach the end of the string. error. unbalanced )
Syntax Parsing A much more complex version of Parentheses checking Basically this is one of the functions of a compiler Syntax parsing Type Checking Assembly/machine code generation.
Stacks and Post Fix Notation We can use Stacks run complex arithmetic expressions, but in with infix notation. We are accustomed to writing expressions using infix notation, such as: Z = X + Y. Stack arithmetic requires that we use postfix notation: Z = XY+. This is also called reverse Polish notation, (somewhat) in honor of its Polish inventor, Jan Lukasiewicz (1878 - 1956). There is also PreFix notation (also called Polish Notation), invented by Jan. X + Y is written + X Y
Postfix The principal advantage of postfix notation is that parentheses are not used. For example, the infix expression, Z = (X Y) + (W U), becomes: Z = X Y W U + in postfix notation.
Infix to Postfix Example: Convert the infix expression (2+3) - 6/3 to postfix: The sum 2 + 3 in parentheses takes precedence; we replace the term with 2 3 +. 2 3+ - 6/3
Infix to Postfix (2) Example: Convert the infix expression (2+3) - 6/3 to postfix: The division operator takes next precedence; we replace 6/3 with 6 3 /. 2 3+ - 6 3/
Infix to Postfix (3) Example: Convert the infix expression (2+3) - 6/3 to postfix: The quotient 6/3 is subtracted from the sum of 2 + 3, so we move the - operator to the end. 2 3+ 6 3/ -
Converting infix to postfix algorithm A simplified version of the Shunting-yard algorithm (complete version) For all the input tokens: Read the next token; If token is an operator (x): While there is an operator (y) at the top of the operators stack and either (x) is left-associative and its precedence is less or equal to that of (y), or (x) is right-associative and its precedence is less than (y): Pop (y) from the stack; Add (y) output buffer; Push (x) on the stack; Else If token is left parenthesis, then push it on the stack; Else If token is a right parenthesis: Until the top token (from the stack) is left parenthesis, pop from the stack to the output buffer; Also pop the left parenthesis but don t include it in the output buffer; Else add token to output buffer. While there are still operator tokens in the stack, pop them to output
Expression Evaluation: Postfix arithmetic operations Using a stack and Postfix, the math is very simple. Given a postfix expression. push operands onto the stack pop twice for operators. do the math push the result back onto the stack. The final result will be the only item on the stack.
Stack Operations Example: Use a stack to evaluate the postfix expression 2 3 + 6 3 / - 2 3 + 6 3 / - Scanning the expression from left to right, push operands onto the stack, until an operator is found 3 2
Stack Operations Example: Use a stack to evaluate the postfix expression 2 3 + 6 3 / - 2 3 + 6 3 / - Pop the two operands and carry out the operation indicated by the operator. Push the result back on the stack. 5
Stack Operations Example: Use a stack to evaluate the postfix expression 2 3 + 6 3 / - 2 3 + 6 3 / - Push operands until another operator is found. 3 6 5
Stack Operations Example: Use a stack to evaluate the postfix expression 2 3 + 6 3 / - 2 3 + 6 3 / - Carry out the operation and push the result. 2 5
Stack Operations Example: Use a stack to evaluate the postfix expression 2 3 + 6 3 / - 2 3 + 6 3 / - Finding another operator, carry out the operation and push the result. The answer is at the top of the stack. 3
String Reversal Using a stack how would we do this?
Writing a stack We need to implement push(), pop(), front() [sometimes called top() or peek()], isEmpty() and size() And we already have a linked list. So instead of starting from scratch use inheritance.
inheritance for stack operations void push( data ) calls what method already written? void pop() calls what method already written? data front() May need to be written. Remember peek just returns the value of the top of the stack bool isEmpty() call what method already written? or no override if we just use the empty method from linked lists. int size() calls what method already written? or no override needed, just use the size method in linked lists.
Using inheritance! template<typename T> class myStack: public myList<T> { public: //No changes needed for isEmtpy() or Size() void push(T item) { myList<T>::insert(item); }
Using inheritance! (2) T front() { if (myList<T>::head != nullptr) return myList<T>::head->data; else return nullptr; } bool pop() { if ( myList<T>::head != nullptr) { myList<T>::remove(); return true; } else return false; } };
efficiency of stack operations How fast are these operations? Do they run in constant time or does the run time change depending on the length of the list? push? pop? peek? empty and size?
QA &
