In Postfix expression operators are written after their operands. For example, the expressions given are in postfix notation A B C + * D /.
Point to consider
- Permitted operands: A,B,C,D means any real number is permitted.
- Permitted operators: +,-, *, /, ^(exponentiation)
- Blanks are permitted in the expression
- Parenthesis are permitted
Prefix and Postfix expressions can be evaluated faster in comparison to an infix expression because we don’t need to process any brackets or follow the operator precedence rule. In postfix and prefix expressions whichever operator comes before will be evaluated first, irrespective of its priority. Also, there are no brackets in these expressions. As long as we can guarantee that a valid prefix or postfix expression is used, it can be evaluated with correctness.
Algorithm to evaluate postfix expression
Step 1: If a character is an operand push it to Stack
Step 2: If the character is an operator
Pop two elements from the Stack.
Operate on these elements according to the operator, and push the result back to the Stack
Step 3: Step 1 and 2 will be repeated until the end has reached.
Step 4: The Result is stored at the top of the Stack,
return it
Step 5: End
Complexity of Postfix evaluation
The Postfix evaluation algorithm has linear complexity O(N). Since we scan the expression once and perform push and pop operations which take constant time.