http://www.youtube.com/watch?v=_EyhFWwnvcs
Stack is a first in last out data structure
you can't do selective removal from a stack
selective removal is possible with data structure like array and linked list
push()
pop()
size()
isempty()
top()
to implement stack we use an array
linked list also can be used to implement stack
- Polish notation (prefix notation)
It refers to the notation in which the operator is placed before its two operands . Here no parentheses are required, i.e.,
+AB
Reverse Polish notation(postfix notation) –
It refers to the analogous notation in which the operator is placed after its two operands. Again, no parentheses is required in Reverse Polish notation, i.e.,
AB+
Stack organized computers are better suited for post-fix notation then the traditional infix ntation.
Thus the infix notation must be converted to the post-fix notation. The conversion from infix notation to post-fix notation must take into consideration the operational hierarchy.
Highest: Exponentiation (^)
Next highest: Multiplication (*) and division (/)
Lowest: Addition (+) and Subtraction (-)
Now we need to calculate the value of these arithmetic operations by using stack.
The procedure for getting the result is:
Convert the expression in Reverse Polish notation( post-fix notation).
Push the operands into the stack in the order they are appear.
When any operator encounter then pop two topmost operands for executing the operation.
After execution push the result obtained into the stack.
After the complete execution of expression the final result remains on the top of the stack.
For example –
Infix notation: (2+4) * (4+6)
Post-fix notation: 2 4 + 4 6 + *
Result: 60
From Postfix to Answer
•The reason to convert infix to postfix expression is that we can compute the answer of postfix expression easier by using a stack.
Postfix Expression
•Infix expression is the form AOB
–A and B are numbers or also infix expression
–O is operator ( +, -, *, / )
•Postfix expression is the form ABO
–A and B are numbers or also postfix expression
–O is operator ( +, -, *, / )
From Postfix to Answer
•Algorithm: maintain a stack and scan the postfix expression from left to right–If the element is a number, push it into the stack
–If the element is a operator O, pop twice and get A and B respectively. Calculate BOAand push it back to the stack
–When the expression is ended, the number in the stack is the final answer
Transform Infix to Postfix
•Observation 1: The order of computation depends on the order of operators
–The parentheses must be added according to the priority of operations.
–The priority of operator * and / is higher then those of operation + and –
–If there are more than one equal-priority operators, we assume that the left one’s priority is higher than the right one’s
•This is called left-to-right parsing.
https://faculty.utrgv.edu/john.abraham/6314/assignments/postfix%20tutorial.pdf
Infix to Postfix Conversion
•We use a stack
•When an operand is read, output it
•When an operator is read
–Pop until the top of the stack has an element of lower precedence
–Then push it
•When ) is found, pop until we find the matching (
•( has the lowest precedence when in the stack
•but has the highest precedence when in the input
•When we reach the end of input, pop until the stack is empty
https://cs.nyu.edu/courses/fall10/V22.0102-004/lectures/InfixToPostfixExamples.pdf
- Infix to postfix conversion algorithm
A summary of the rules follows:
1. Print operands as they arrive.
2. If the stack is empty or contains a left parenthesis on top, push the incoming operator onto the stack.
3. If the incoming symbol is a left parenthesis, push it on the stack.
4. If the incoming symbol is a right parenthesis, pop the stack and print the operators until you see a left parenthesis. Discard the pair of parentheses.
5. If the incoming symbol has higher precedence than the top of the stack, push it on the stack.
6. If the incoming symbol has equal precedence with the top of the stack, use association. If the association is left to right, pop and print the top of the stack and then push the incoming operator. If the association is right to left, push the incoming operator.
7. If the incoming symbol has lower precedence than the symbol on the top of the stack, pop the stack and print the top operator. Then test the incoming operator against the new top of stack.
8. At the end of the expression, pop and print all operators on the stack. (No parentheses should remain.)
http://csis.pace.edu/~wolf/CS122/infix-postfix.htm
No comments:
Post a Comment