Problem Statement
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Some examples:
|
1 2 |
["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9 ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6 |
Original LeetCode problem page
My Solution in Swift
A simple stack can be used to solve the problem in linear time O(n)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
func evalRPN(tokens: [String]) -> Int { var stack = [String]() for s in tokens { switch s { case "+": var rightOperand = stack.removeLast().toInt()! var leftOperand = stack.removeLast().toInt()! stack.append(String(leftOperand + rightOperand)) case "-": var rightOperand = stack.removeLast().toInt()! var leftOperand = stack.removeLast().toInt()! stack.append(String(leftOperand - rightOperand)) case "*": var rightOperand = stack.removeLast().toInt()! var leftOperand = stack.removeLast().toInt()! stack.append(String(leftOperand * rightOperand)) case "/": var rightOperand = stack.removeLast().toInt()! var leftOperand = stack.removeLast().toInt()! stack.append(String(leftOperand / rightOperand)) default: stack.append(s) } } return stack.removeLast().toInt()! } |
Try It Yourself
1: each links to a blog post of mine that is dedicated to the problem
2: total execution time of a solution on my MacBook Pro (Late 2013, 2.6 GHz Intel Core i7, 16 GB 1600 MHz DDR3). Each solution is compiled with following command:
$ swiftc -O -sdk `xcrun --show-sdk-path --sdk macosx` json.swift main.swift -o mySolution
The total execution time is the average of 10 runs.
3: these test cases are semi-automatically :P retrieved from LeetCode Online Judge system and are kept in JSON format
4: each Xcode project includes everything (my Swift solution to a problem, its JSON test cases and a driver code to test the solution on those test cases)
| Problem1 | Time2 | Test Cases3 | My Xcode Project4 |
| Evaluate Reverse Polish Notation | 107.186ms |