ZeroJudge F698: Post-Order Operator Evaluation

Normally, when writing expressions, we are accustomed to using infix notation, where the operator is placed between the two operands, such as in “3 + 4”. In 1924, a Polish logician named Jan Łukasiewicz invented prefix notation, where the operator is placed before the operands, as in “+ 3 4”.

Although prefix notation does not align with human reading habits, its advantage is that it does not require any parentheses to clearly specify the order of operations. For example, in our commonly used infix notation:

1 + 2 × 3 = 7

Because multiplication and division are evaluated before addition and subtraction. If you want to evaluate addition and subtraction first, you need to use parentheses, like this:

(1 + 2) × 3 = 9

However, if you use prefix notation, parentheses are not needed:

+ 1 × 2 3 = 7
× + 1 2 3 = 9

Prefix notation is also known as Polish notation (PN).

Later, after computers were invented, engineers discovered that prefix notation consumed more memory during evaluation. In 1954, Arthur Walter Burks introduced postfix notation, where the operator is placed after the operands. This notation, like prefix notation, does not require parentheses to specify different operation orders:

1 2 3 × + = 7
1 2 + 3 × = 9

However, postfix notation can be evaluated very easily using a stack. By processing the operands and operators in sequence, the stack allows for straightforward evaluation without the need for parentheses.

Postfix notation was used in all electronic calculators released by HP in the 1970s and 1980s, and even some models from the 2020s still use it. It is also used in some stack-based programming languages, such as Forth. Here’s a link to a postfix calculator you can try out: http://www.alcula.com/calculators/rpn/.

Postfix notation is also known as Reverse Polish Notation (RPN) or Polish Postfix Notation.

Now, please help evaluate a postfix expression.

Sample Inputs/Outputs

Thought Process

Use a stack to store data and read input via strings until EOF. When a number is received, push it onto the stack. When a non-number is received, pop the top two elements from the stack to perform the calculation, remembering that the first popped element is the second operand (e.g., for addition, it is the second number). After the calculation, push the result back onto the stack. At the end, there should be only one number left in the stack, which should be output.

Sample Code－ZeroJudge F698: Post-Order Operator Evaluation

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

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    string str;
    stack<string>sb;
    while (cin >> str) {
        if (str == "+" || str == "-" || str == "*" || str == "/") {
            const int b = stoi(sb.top());
            sb.pop();
            const int a = stoi(sb.top());
            sb.pop();
            if (str == "+") sb.push(to_string(a + b));
            else if (str == "-") sb.push(to_string(a - b));
            else if (str == "*") sb.push(to_string(a * b));
            else if (str == "/") sb.push(to_string(a / b));
        }
        else {
            sb.push(str);
        }
    }
    cout << sb.top() << "\n";
}

//ZeroJudge F698
//Dr. SeanXD