Evaluate given postfix expression

Write code to efficiently evaluate given postfix expression.

 

For example,


82/ will evaluate to 4 (8/2)

138*+ will evaluate to 25 (1+8*3)

545*+5/ will evaluate to 5 ((5+4*5)/5)
 


 
We can easily compute the value of postfix expression by using a stack. The idea is to traverse the given expression from left to right. If the current character of the expression is an operand, we push it to the stack else if current character is a operator we pop top two elements from the stack, evaluate them using the current operator and push the result back to the stack. When all characters of the expression are processed, we will be left with only one element in the stack that contains the evaluate value.

 
C++ implementation –
 

Download   Run Code

Output:

25

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).
 

Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂