Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Stack & Queue

Evaluate Postfix Expression

Medium · Stack & Queue · Asked at Amazon, Microsoft, LinkedIn, TCS, Infosys

Evaluate an expression in postfix (Reverse Polish) notation. Tokens are integers and + - * /. Division truncates toward zero.

Input

One line of space-separated tokens.

Output

The value of the expression.

Constraints

Push numbers on a stack; for an operator pop b, then a, and push a op b.

Example 1

Input

2 1 + 3 *

Output

9

Example 2

Input

4 13 5 / +

Output

6

Hints

  1. Numbers wait on a stack until an operator needs them.
  2. For an operator, pop b first and then a (order matters for − and /), and push a op b. Watch out: "-3" is a number, not an operator.

Approach

Read tokens one by one. A token is an operator only if it is exactly one of + - * /. Anything else, such as "-3", is a number and gets pushed. For an operator, pop the right operand b, then the left operand a, and push the result. Division must truncate toward zero: C++/Java / already does, but Python's // floors, so the Python version divides the absolute values and fixes the sign. The single value left at the end is the answer.

Complexity: O(tokens) time · O(tokens) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<long long> st;
    string tok;
    while (cin >> tok) {
        if (tok == "+" || tok == "-" || tok == "*" || tok == "/") {
            long long b = st.back(); st.pop_back();
            long long a = st.back(); st.pop_back();
            if (tok == "+") st.push_back(a + b);
            else if (tok == "-") st.push_back(a - b);
            else if (tok == "*") st.push_back(a * b);
            else st.push_back(a / b);  // C++ division truncates toward zero
        } else {
            st.push_back(stoll(tok));
        }
    }
    cout << st.back() << "\n";
    return 0;
}

Python solution

stack = []
for tok in input().split():
    if tok in ("+", "-", "*", "/"):
        b = stack.pop()
        a = stack.pop()
        if tok == "+":
            stack.append(a + b)
        elif tok == "-":
            stack.append(a - b)
        elif tok == "*":
            stack.append(a * b)
        else:
            q = abs(a) // abs(b)  # truncate toward zero, like C++/Java
            stack.append(q if (a < 0) == (b < 0) else -q)
    else:
        stack.append(int(tok))
print(stack[-1])

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        ArrayDeque<Long> st = new ArrayDeque<>();
        while (sc.hasNext()) {
            String tok = sc.next();
            if (tok.equals("+") || tok.equals("-") || tok.equals("*") || tok.equals("/")) {
                long b = st.pop(), a = st.pop();
                switch (tok) {
                    case "+": st.push(a + b); break;
                    case "-": st.push(a - b); break;
                    case "*": st.push(a * b); break;
                    default: st.push(a / b);  // Java division truncates toward zero
                }
            } else {
                st.push(Long.parseLong(tok));
            }
        }
        System.out.println(st.peek());
    }
}

Solve Evaluate Postfix Expression online · All practice problems