Start learning free

LESSON 397 OF 540 · STACK

Evaluate Reverse Polish Notation in Go: O(n) with a Stack

Practice O(n) Read the full explanation

In reverse Polish notation, also called postfix notation, an operator comes after its two operands: 3 + 4 is written 3 4 +, and (1 + 2) * 3 is written 1 2 + 3 *. It needs no parentheses: the order of the tokens alone says what is computed first.

Given an array of strings tokens that holds a valid expression in reverse Polish notation, return the value of the expression.

  • Each token is either an operator, "+", "-", "*" or "/", or an integer such as "42" or "-7".
  • An operator works on the two values that come right before it, once those are worked out: the first of them is its left operand and the second its right operand. 8 3 - is 8 - 3 = 5, not 3 - 8.
  • The division of two integers truncates toward zero: it drops the fraction, so 7 / 2 is 3 and -7 / 2 is -3 (not -4).

 

Example 1:

Input: tokens = ["2", "1", "+", "3", "*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Example 2:

Input: tokens = ["4", "13", "5", "/", "+"]
Output: 6
Explanation: (4 + (13 / 5)) = 4 + 2 = 6, because 13 / 5 is 2.6, truncated to 2.

Example 3:

Input: tokens = ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
Output: 22
Explanation:
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 22
6 / -132 is about -0.045, and truncating it toward zero gives 0.

 

Constraints:

  • 1 <= tokens.length <= 105
  • tokens[i] is "+", "-", "*", "/", or an integer.
  • Every integer in tokens, and every value computed along the way, fits in a 32-bit signed integer: from -231 to 231 - 1.
  • tokens is a valid expression in reverse Polish notation, and no division is by zero.

Note:

Your algorithm should run in O(n) time and use O(n) extra space, where n is the number of tokens.

STEP 1 OF 12
    Ctrl + Enter to check

    GO · STACK

    Evaluate Reverse Polish Notation in Go, explained

    Problem overview

    In reverse Polish notation, also called postfix notation, an operator comes after its two operands. The expression 3 + 4 is written 3 4 +, and (1 + 2) * 3 is written 1 2 + 3 *. No parentheses are needed: the order of the tokens alone says what is computed first.

    The function evalRPN(tokens []string) int receives a valid expression as a slice of strings and returns its value. Each token is one of the operators "+", "-", "*", "/", or an integer such as "42" or "-7". An operator works on the two values right before it: the first is its left operand and the second its right operand, so 8 3 - is 8 - 3 = 5. Division truncates toward zero, so 7 / 2 is 3 and -7 / 2 is -3.

    For ["2", "1", "+", "3", "*"] the answer is 9, because (2 + 1) * 3 = 9. For ["4", "13", "5", "/", "+"] it is 6, because 13 / 5 truncates to 2 and 4 + 2 = 6.

    The lesson asks for O(n) time and O(n) extra space, where n is the number of tokens.

    Approach: a stack of values

    Read the tokens from left to right. A number can't be used until an operator asks for it, so it waits. When an operator arrives, the two values it needs are the two most recent values that haven't been used yet. That is exactly the top of a stack: the last value pushed is the first one taken off.

    The rule is short:

    • A number: push it.
    • An operator: pop two values, combine them, and push the result back. The result takes the place of its two operands, so a later operator can use it.

    Every operator turns two values into one. A valid expression therefore ends with exactly one value on the stack, and that is the answer.

    Here is the stack for ["2", "1", "+", "3", "*"] after each token:

    2 [2]
1 [2 1]
+ [3]
3 [3 3]
* [9]

    The + pops 1 and 2 and pushes 3. The * pops 3 and 3 and pushes 9.

    The order of the two pops matters. The right operand was pushed last, so it comes off first. Name it b, pop the left operand into a second, and compute a - b or a / b: for 8 3 - that gives 8 - 3, not 3 - 8.

    Step by step

    1. Create the stack: stack := []int{}, an empty slice of integers. Its end is the top of the stack: append pushes there, and reslicing pops from there.
    2. Loop over the tokens with for _, token := range tokens. Each token is read once, so the whole evaluation is O(n).
    3. Test for an operator by comparing token with "+", "-", "*" and "/", joined with ||. A negative number like "-7" starts with a minus sign, but it is not equal to the one-character token "-".
    4. Pop the right operand: b := stack[len(stack)-1] reads the top, and stack = stack[:len(stack)-1] drops it.
    5. Pop the left operand into a the same way.
    6. Add: if token == "+", stack = append(stack, a+b). The result goes back on the stack, and append's result must be stored.
    7. Subtract: an else if for "-" pushes a-b. The order matters here.
    8. Multiply: an else if for "*" pushes a*b.
    9. Divide: the last else covers "/" and pushes a/b.
    10. Parse a number: the else of the first if handles every other token. num, _ := strconv.Atoi(token) converts the string to an int. The blank identifier ignores the error, since the remaining tokens are valid integers.
    11. Push it: stack = append(stack, num).
    12. Return the result: after the loop, stack[len(stack)-1] is the one value left.

    The solution in Go

    func evalRPN(tokens []string) int {
    stack := []int{}
    for _, token := range tokens {
        if token == "+" || token == "-" || token == "*" || token == "/" {
            b := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            a := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            if token == "+" {
                stack = append(stack, a+b)
            } else if token == "-" {
                stack = append(stack, a-b)
            } else if token == "*" {
                stack = append(stack, a*b)
            } else {
                stack = append(stack, a/b)
            }
        } else {
            num, _ := strconv.Atoi(token)
            stack = append(stack, num)
        }
    }
    return stack[len(stack)-1]
}

    The Go details worth a closer look:

    • A slice as a stack. append(stack, v) pushes. stack[:len(stack)-1] is the slice without its last element and pops without copying anything. Go has no built-in stack type, and this is the usual idiom.
    • Integer division truncates toward zero. In Go, -7 / 2 is -3 and 7 / -2 is -3, exactly as the lesson requires, so no adjustment is needed. For comparison, -7 % 2 is -1: the remainder takes the sign of the dividend.
    • strconv.Atoi returns two values. It returns the number and an error. "-11" parses to -11 with a nil error, and a leading minus sign is fine. "+" would fail with strconv.Atoi: parsing "+": invalid syntax and return 0, which is why the operators are handled before the parsing.
    • Unused values. Go refuses to compile unused variables, so the ignored error is written as _ instead of a name.
    • int is 64 bits. The lesson guarantees every value fits in 32 bits, so the solution never needs to worry about overflow. In Go, 2147483647 + 1 in an int is simply 2147483648.
    • Strings compare by value. token == "+" compares the contents, so it works as expected.

    Complexity

    Time: O(n). Each token is read once, and each push, pop and arithmetic operation takes constant time. Parsing a number costs time proportional to its length, which is bounded because the integers fit in 32 bits.

    Space: O(n). In the worst case, such as 1 2 3 4 + + +, nearly all the numbers are on the stack before the first operator arrives.

    Edge cases and common mistakes

    • A single number. ["42"] gives 42 and ["-7"] gives -7. There is no operator, and the stack holds one value.
    • Operand order. ["8", "3", "-"] gives 5. Popping into a first and b second computes 3 - 8 and gives -5.
    • Negative numbers. "-11" is a number, not an operator. The comparison with "-" is against the whole token, so it works.
    • Division toward zero. ["7", "2", "/"] gives 3, ["-7", "2", "/"] gives -3, ["7", "-2", "/"] gives -3 and ["-7", "-2", "/"] gives 3. A language that floors instead would give -4 for the second one.
    • A result of zero from a small fraction. ["6", "-132", "/"] gives 0, because the fraction of about -0.045 is truncated.
    • Forgetting to store append's result. Writing append(stack, a+b) alone is a compile error in Go, because the result is not used. The grown slice must be assigned back to stack.
    • Using the wrong end. The values to combine are at the end of the slice. Reading stack[0] takes the oldest value, not the newest.
    • Treating tokens as characters. A token like "13" has two characters, so the code can't look at one byte. It compares whole strings and parses with strconv.Atoi.

    Testing

    • ["2", "1", "+", "3", "*"] gives 9.
    • ["4", "13", "5", "/", "+"] gives 6.
    • ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"] gives 22.
    • ["8", "3", "-"] gives 5.
    • ["7", "2", "/"] gives 3, and ["-7", "2", "/"] gives -3.
    • ["42"] gives 42.
    • ["6", "-132", "/"] gives 0.
    Keep going with Go500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free