Start learning free

LESSON 398 OF 541 · STACK

Evaluate Reverse Polish Notation in Swift: 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 <= 10⁵
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 -2³¹ to 2³¹ - 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 11

Guided

Ctrl + Enter to check

SWIFT · STACK

Evaluate Reverse Polish Notation in Swift, explained

Problem overview

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 *. No parentheses are needed, because the order of the tokens alone says what is computed first.

evalRPN receives tokens, an array of strings that holds a valid expression, and returns its value as an Int. Each token is an operator ("+", "-", "*" or "/") or an integer such as "42" or "-7". An operator works on the two values right before it, once they are worked out: the first is its left operand and the second its right operand, so 8 3 - is 8 - 3 = 5, not 3 - 8. Division truncates toward zero: 7 / 2 is 3 and -7 / 2 is -3.

For ["2", "1", "+", "3", "*"] the answer is 9, which is (2 + 1) * 3. For ["4", "13", "5", "/", "+"] it is 6, because 13 / 5 is 2 and 4 + 2 is 6. The task asks for O(n) time and O(n) extra space for n tokens.

Approach: a stack of finished values

Read the tokens left to right. A number can't be used until an operator arrives, so it waits. When an operator arrives, its two operands are the two most recent values not yet used: exactly the top two values of a stack. Take them off, compute, and push the result back, where it takes the place of its two operands and can be an operand for a later operator.

Every number pushes one value and every operator replaces two values by one, so a valid expression ends with exactly one value on the stack, the answer. Each token is handled once, so the time is O(n).

Here is the first example, with the stack after each token:

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

Step by step

Create the stack: var stack: [Int] = []. An array works as a stack when you use its end as the top, with append and removeLast().
Loop over the tokens with for token in tokens.
Detect an operator: compare token with "+", "-", "*" and "/", joined with ||. A negative number such as "-7" starts with a minus sign too, but it isn't equal to the one-character token "-", so it counts as a number.
Pop the right operand: let b = stack.removeLast(). It was worked out last, so it is on top.
Pop the left operand: let a = stack.removeLast(). Popping b first and a second keeps the order the expression means.
Plus: if the token is "+", append a + b.
Minus: else if "-", append a - b. Here the order matters.
Times: else if "*", append a * b.
Divide: in the final else, append a / b. Only "/" is left.
Numbers: the outer else appends Int(token)!. A number is its own value and waits on the stack.
Return the result: after the loop, return stack.removeLast(), the one value left.

The solution in Swift

class Solution {
    func evalRPN(_ tokens: [String]) -> Int {
        var stack: [Int] = []
        for token in tokens {
            if token == "+" || token == "-" || token == "*" || token == "/" {
                let b = stack.removeLast()
                let a = stack.removeLast()
                if token == "+" {
                    stack.append(a + b)
                } else if token == "-" {
                    stack.append(a - b)
                } else if token == "*" {
                    stack.append(a * b)
                } else {
                    stack.append(a / b)
                }
            } else {
                stack.append(Int(token)!)
            }
        }
        return stack.removeLast()
    }
}

Swift details worth knowing:

Int(token) returns an optional. It gives nil when the string isn't a number: Int("42") is Optional(42), Int("-7") is Optional(-7), and Int("+") is nil. Every token that reaches this line is an integer, so ! unwraps it safely.
Integer division truncates toward zero. 7 / 2 is 3, -7 / 2 is -3 and 7 / -2 is -3. That is what the task asks for, so the plain / operator needs no extra rounding code.
removeLast() pops from the end and returns the removed element. On an empty array it stops the program, which can't happen for a valid expression.
64-bit Int. The lesson's values fit in 32 bits, and Swift's Int has 64, so these sums and products never overflow here. If an Int operation did overflow, the program would stop rather than wrap.
String comparison. token == "+" compares the contents of the strings, so no special method is needed.

Complexity

Time: O(n). Each token is read once, and each push, pop and arithmetic operation takes constant time.

Space: O(n). In the worst case, for example when all the numbers come before all the operators, the stack holds about half of the tokens at once.

Edge cases and common mistakes

Swapped operands. If a and b are popped in the wrong order, ["8", "3", "-"] gives -5 instead of 5. The solution returns 5, and ["3", "8", "-"] returns -5. Division has the same problem.
Division rounding. ["7", "2", "/"] gives 3, ["-7", "2", "/"] gives -3 and ["7", "-2", "/"] gives -3. A floor division would give -4 for the second one.
Mistaking negative numbers for operators. The token "-7" is a number, and ["-7"] alone returns -7. Test the whole token against "-", not just its first character.
A single number. ["42"] has no operator, and the answer is 42, the one value the final removeLast() finds.
Zero from division. In the lesson's third example, 6 / -132 truncates to 0, and the whole expression comes to 22. The result of a division can be 0 without anything being wrong.
Large values. ["2147483647", "2", "*"] returns 4294967294, which is beyond 32 bits. The lesson's inputs stay within 32 bits, but Swift's 64-bit Int handles bigger values anyway.

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.
["1", "-1", "-"] gives 2.

Keep going with Swift500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free