Challenge: Postfix Calculator

Lab C++ Intermediate 20 points

Evaluate a postfix expression (operator after its two numbers, e.g. 5 1 2 + 4 * + 3 - = 14) with a stack. The expression has n tokens. / is whole-number division.

Input

Line 1: n. Line 2: n tokens: whole numbers and + - * /.

Output

The result.

Example

Input

3
3 4 +

Output

Sample input available Sample output available

Editor

C++

Hints

Numbers go on the stack (stoll turns text into a number).

For an operator: pop b, then a, push a op b.

Solution explanation

The first value popped is the right operand – order matters for − and /.

Show solution

#include <iostream>
#include <stack>
#include <string>
using namespace std;

int main() {
    int n;
    cin >> n;
    stack<long long> s;
    for (int i = 0; i < n; i++) {
        string tok;
        cin >> tok;
        if (tok == "+" || tok == "-" || tok == "*" || tok == "/") {
            long long b = s.top(); s.pop();
            long long a = s.top(); s.pop();
            if (tok == "+") s.push(a + b);
            else if (tok == "-") s.push(a - b);
            else if (tok == "*") s.push(a * b);
            else s.push(a / b);
        } else {
            s.push(stoll(tok));
        }
    }
    cout << s.top() << endl;
    return 0;
}

Output

Answer