/ * *
The title
Evaluate the expression according to the inverse Polish notation.
Valid operators include +, -, *, /. Each operand can be an integer or another inverse Polish expression. Note: Integer division retains only integer parts. Given the inverse Polish expression is always valid. In other words, the expression always yields a valid value and never has a divisor of 0.
Example 1:
Input: [” 2 “, “1”, “+”, “3”, “*”] output: 9: the formula into common infix arithmetic expression is: ((2 + 1) * 3) = 9 example 2:
Input: [” 4 “, “13”, “5”, “/”, “+”] output: 6: this formula into common infix arithmetic expression is: (4 +) (13/5) = 6 example 3:
Input: [” 10 “, “6”, “9”, “3”, “+”, “11”, “”,”/”, “”,” 17 “, “+”, “5”, “+”] output: 22: The formula is converted to a common infix arithmetic expression: ((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 = 17 + 5 = 22
Inverse Polish expression:
An inverse Polish expression is an expression with a suffix, which means the operator is written after it.
The usual formula is an infix expression, such as (1 + 2) * (3 + 4). The inverse Polish expression of the formula is (1 2 +) (3 4 +) *). The inverse Polish expression has two main advantages:
After removing the parentheses, the expression has no ambiguity. Even if the above formula is written as 1, 2 + 3, 4 + *, the correct result can be calculated according to the order. Suitable for stack operation: the number is pushed into the stack; When encountering an operator, the top two numbers on the stack are calculated and the result is pushed onto the stack.
Source: LeetCode link: leetcode-cn.com/problems/ev… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.
The test code
print(evalRPN([“2”, “1”, “+”, “3”, “*”]))
notes
And the whole point of this problem is to take advantage of the properties of the stack not just the operator but the operator, take the top two elements of the stack, do the operation, and then push the result onto the stack notice second plus, minus, multiply and divide first because second is the element that was pushed first and first is probably the element that was added after the last operation
The code address
Github.com/zmfflying/Z… * /
The problem solving code
import Foundation func evalRPN(_ tokens: [String]) - > Int {/ var/stack path: [Int] = (Int) (a) / / String let dic recorded four operators: [String: Int] = [" + ": 1," - ": 1," * ": 1,"/" : Var second: Int = 0 for tokens in tokens {if dic[token]! = nil {first = path.removelast () second = path.removelast ( token { case "+": path.append(second + first) break case "-": path.append(second - first) break case "*": path.append(second * first) break case "/": path.append(second / first) break default: break } } else { if let num = Int(token) { path.append(num) } } } return path.count == 0 ? 0 : path.first! }Copy the code