PostFIx Expression:
What is a postfix expression?????
An expression that has values followed by operators are called postfix expressions. It is also known as Polish notation.
Example: a b c * + d -
It can be evaluated as: (a + b * c )- d.
lets see how to evaluate a postfix expression using stack . Before that it is recommended to have a small recap about the stack operations. To see that please click here: Stack operations.
How to evaluate a PostFix operation using Stack?????
Algorithm to evaluate a postfix expression:
Step 1: Create an empty stack. Read each input sequentially one by one.
Step 2: While reading the input, if the input is a value then push it into the stack.
Step 3: If the input is a symbol, then perform the respected operation among the recently pushed two elements in the stack.
After performing the operation delete those two elements from stack using pop operation.
Store the result into the stack by pushing that element at the top of the stack.
Step 4: Repeat steps 2 and 3 until the expression ends.
Step 5: After completing the expression, check if the stack has more than one element.
If the stack has only one element, then that will be the result of the expression that is evaluated. Otherwise, there is some error in the expression. The expression is not a balanced one.
EXAMPLE:
Lets try this algorithm using an example expression.
Consider the following expression as an example. Let us evaluate that using a stack.
Expression: 10 5 6 * + 1 -
What is a postfix expression?????
An expression that has values followed by operators are called postfix expressions. It is also known as Polish notation.
Example: a b c * + d -
It can be evaluated as: (a + b * c )- d.
lets see how to evaluate a postfix expression using stack . Before that it is recommended to have a small recap about the stack operations. To see that please click here: Stack operations.
How to evaluate a PostFix operation using Stack?????
Algorithm to evaluate a postfix expression:
Step 1: Create an empty stack. Read each input sequentially one by one.
Step 2: While reading the input, if the input is a value then push it into the stack.
Step 3: If the input is a symbol, then perform the respected operation among the recently pushed two elements in the stack.
After performing the operation delete those two elements from stack using pop operation.
Store the result into the stack by pushing that element at the top of the stack.
Step 4: Repeat steps 2 and 3 until the expression ends.
Step 5: After completing the expression, check if the stack has more than one element.
If the stack has only one element, then that will be the result of the expression that is evaluated. Otherwise, there is some error in the expression. The expression is not a balanced one.
EXAMPLE:
Lets try this algorithm using an example expression.
Consider the following expression as an example. Let us evaluate that using a stack.
Expression: 10 5 6 * + 1 -
Step 1: Create an empty stack:
Step 2: Insert first element 10
- Reads the first element, 10.
- The first element, 10 is pushed into the stack at the top.
Step 3: Push second element 5
- Reads the second element, 5.
- The second element, 5 is pushed into the stack.
Step 4: push third element 6
- Reads the third element, 6.
- The third element, 6 is pushed into the stack.
Step 5: Read Symbol. Perform operation:
- Reads the next element, a symbol *.
- It is not a value.It is a symbol. Hence it performs the operation * (multiplication) between the recently inserted two elements (6 * 5 =30). Pop those two elements after performing operation.
- The result of the operation 30 is again stored in the stack by pushing it at the top.
- Now the stack has two elements 10 and 30 with 30 at its top.
Step 6: read symbol +
- Read the next element, a symbol +.
- It is also a symbol. Hence perform addition operation between the two elements of the stack from the top.(30 + 10 = 40). Then pop those elements from the stack.
- Store the result 40 in the stack by pushing it at the top.
Step 7: read 1
- Read the next element, a value: 1
- Push it into the stack.
Step 8: read symbol '-'
- Read the input operator '-'.
- Perform operation 40-1=39.
- Pop elements 40 and 1 from stack.
- Store result 39 by pushing it into the stack at the top.
Step 9:
Check the stack if it has more than one element.
If so then there is some error.
Otherwise the single element left in the stack is the result of the expression evaluated.
Thus the usage of stack in evaluating a postfix expression is seen in detail.
Advantages of evaluating postfix expression using stack algorithm:
It is very simple.
The time taken is constant O(N), as it uses stack.
As it is a postfix expression there is no need to see for any precedence rules. Hence the algorithm is simple and fast.
