Reverse Polish Notation

Before we get to reverse polish notation, let's first see what is infix notation.

Infix notation is the arithmatic expression we use every day, like below.

3 + 4

As you can see, the feature of infix notation is the operators are placed between operands.

Polish notation is a mathematical notation in which operators precede their operands.

+ 3 4

Reverse polish notation is a mathematical notation in which operators follow their operands.

3 4 +

As you may ask, we use infix notation every day, why would we should consider polish notation?

Well, one reason is that, considering a expression like below:

5 * 4 + 9 - 2 / 3 + 1

It's a pretty long infix notation expression, which contains a few different operators. To evaluate this expression properly, we need to know which operators should go first, and which should go next. So we need to learn another priority rule first.

If we use polish notation, there is no need for that. We just follow a specific process and we can evaluate the expression correctly.

Evaluate Reverse Polish Notation

Take leetcode Evaluate Reverse Polish Notation as an example, let's see how to evaluate polish notation.

Basically, there are two ways to solve this problem.

The first way is edit the array in-place. Specifically, we search for the left first operator, and take two number before the operator as operands. And then delete this 3 elements and insert the evaluation result into array.

A simple example gos like below.

1, 2, *, 3, 4, -, /, 5, +

x=1,y=2,op=*,z=1*2=3

3,3,4,-,/,5,+

x=3,y=4,op=-,z=3-4=-1

3,-1,/,5,+

x=3,y=-1,op=/,z=3/-1=-3

-3,5,+

x=-3,y=5,op=+,z=-3+5=2

2

Then let's see this process in code.

function evalRPN(tokens: string[]): number {
    let x: number;
    let y: number;
    let z: number;
    let i: number;

    const ops: Record<string, any> = {
        "+": (x: number, y: number) => x + y,
        "-": (x: number, y: number) => x - y,
        "*": (x: number, y: number) => x * y,
        "/": (x: number, y: number) => ~~(x / y),
    };

    while (tokens.length > 1) {
        i = 0;
        while (i < tokens.length) {
            if (tokens[i] in ops) break;
            i += 1;
        }

        x = parseInt(tokens[i - 2]);
        y = parseInt(tokens[i - 1]);
        z = ops[tokens[i]](x, y);
        tokens.splice(i - 2, 3, z.toString());
    }

    return parseInt(tokens[0]);

};

The second way to solve this problem is to use a stack. The process is a pretty classic stack process. Loop the array, every time we see a number, push it into stack, every time we see a operator, pop 2 numbers from stack, evaluate them, and push the evaluated result into the stack. At last, there should be only 1 element in the stack, which is the final result.

function evalRPN(tokens: string[]): number {
    const stack: string[] = [];
    let x: number;
    let y: number;
    let z: number;

    const ops = {
        "+": (x: number, y: number) => x + y,
        "-": (x: number, y: number) => x - y,
        "*": (x: number, y: number) => x * y,
        "/": (x: number, y: number) => ~~(x / y),
    };
    for (const token of tokens) {
        switch (token) {
            case "+":
            case "-":
            case "*":
            case "/":
                y = parseInt(stack.pop() as string);
                x = parseInt(stack.pop() as string);
                z = ops[token](x, y);
                stack.push(z.toString());
                break;
            default:
                stack.push(token);
        }
    }

    return parseInt(stack[0]);
};