Evaluate a postfix expression
Write code to evaluate a given postfix expression efficiently.
For example,
138*+ will evaluate to 25 (1+8*3)
545*+5/ will evaluate to 5 ((5+4*5)/5)
Assume that the postfix expression contains only single-digit numeric operands, without any whitespace.
We can easily compute a postfix expression by using a stack. The idea is to traverse the given postfix expression from left to right. If the current character of the expression is an operand, push it into the stack; otherwise, if the current character is an operator, pop the top two elements from the stack, evaluate them using the current operator and push the result back into the stack. When all the expression characters are processed, we will be left with only one element in the stack containing the value of a postfix expression.
Following is the implementation in C++, Java, and Python based on the above idea:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
#include <iostream> #include <string> #include <stack> using namespace std; // Function to evaluate a given postfix expression int evalPostfix(string exp) { // create an empty stack stack<int> stack; // traverse the given expression for (char c: exp) { // if the current character is an operand, push it into the stack if (c >= '0' && c <= '9') { stack.push(c - '0'); } // if the current character is an operator else { // remove the top two elements from the stack int x = stack.top(); stack.pop(); int y = stack.top(); stack.pop(); // evaluate the expression 'x op y', and push the // result back to the stack if (c == '+') { stack.push(y + x); } else if (c == '-') { stack.push(y - x); } else if (c == '*') { stack.push(y * x); } else if (c == '/') { stack.push(y / x); } } } // At this point, the stack is left with only one element, i.e., // expression result return stack.top(); } int main() { string exp = "138*+"; cout << evalPostfix(exp); return 0; } |
Output:
25
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
import java.util.Stack; class Main { // Function to evaluate a given postfix expression public static int evalPostfix(String exp) { // base case if (exp == null || exp.length() == 0) { System.exit(-1); } // create an empty stack Stack<Integer> stack = new Stack<>(); // traverse the given expression for (char c: exp.toCharArray()) { // if the current character is an operand, push it into the stack if (Character.isDigit(c)) { stack.push(c - '0'); } // if the current character is an operator else { // remove the top two elements from the stack int x = stack.pop(); int y = stack.pop(); // evaluate the expression 'x op y', and push the // result back to the stack if (c == '+') { stack.push(y + x); } else if (c == '-') { stack.push(y - x); } else if (c == '*') { stack.push(y * x); } else if (c == '/') { stack.push(y / x); } } } // At this point, the stack is left with only one element, i.e., // expression result return stack.pop(); } public static void main(String[] args) { String exp = "138*+"; System.out.println(evalPostfix(exp)); } } |
Output:
25
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
from collections import deque # Function to evaluate a given postfix expression def evalPostfix(exp): # base case if not exp: exit(-1) # create an empty stack stack = deque() # traverse the given expression for ch in exp: # if the current is an operand, push it into the stack if ch.isdigit(): stack.append(int(ch)) # if the current is an operator else: # remove the top two elements from the stack x = stack.pop() y = stack.pop() # evaluate the expression 'x op y', and push the # result back to the stack if ch == '+': stack.append(y + x) elif ch == '-': stack.append(y - x) elif ch == '*': stack.append(y * x) elif ch == '/': stack.append(y // x) # At this point, the stack is left with only one element, i.e., # expression result return stack.pop() if __name__ == '__main__': exp = '138*+' print(evalPostfix(exp)) |
Output:
25
The time complexity of the above solution is O(n) and requires O(n) extra space, where n is the length of the postfix expression.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)