Leetcode link to the original problem

Evaluate the expression according to the inverse Polish notation.

Valid operators include +,-,*,/. Each operand can be an integer or another inverse Polish expression.

Description:

Integer division preserves 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"."*"((2 + 1) * 3) = 9Copy the code

Example 2:

Input:"4"."13"."5"."/"."+"(4 + (13/5)) = 6Copy the code

Example 3:

Input:"10"."6"."9"."3"."+"."11"."*"."/"."*"."17"."+"."5"."+"]
输出: 22
解释: 
  ((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
Copy the code

concept

There are a couple of concepts that you need to understand.

1, operands (numbers) 2, operators (as the name suggests) 3, delimiters (parentheses) Note that there is no need to argue with parentheses

Parentheses are also used to calculate the parentheses (of course, his questions may not have parentheses)

Ok, so once we understand this concept we need to understand something called postfix expressions.

The calculation problem that we saw on the exam paper that format is the infix expression, and you can tell where to calculate first and then where to calculate intelligences. But machines can’t do it. Machines can only do it by following certain rules, so we need to introduce something in order called postfix expressions.

Here’s an example: 6*(3+5)/8 = 6; This is an infix expression. 3, 5 plus 6 times 8 over is 6; This is the suffix expression.

In infix expressions, we see that we need to calculate 3+5 first, whereas in postfix expressions, the 3 and 5 come first and the operator comes last. And so on, this is the suffix expression. The prefix expression you can look at for yourself, it’s pretty much the same as the suffix expression.

Train of thought

Because what he’s putting in is strings and strings, so we’re going to turn strings into numbers and strings may not be operands exactly, they may be operators (there’s no delimiters here)

Make a result stack, which is used to store the operation and the result, and finally the stack has only one element, which is the final answer.

If it’s a +,-,*,/, that means it’s an operator, so I’m going to push the top two elements of the stack off the stack, assign them to num1, num2, and throw them to the function,

Notice, if it is subtraction and division that have to reverse, stack in the stack out of the stack order is the opposite!

We’re going to push the result back onto the stack so we can run into the operator the next time.

And so on, stack.top() is the end result!

func evalRPN(_ tokens: [String]) -> Int {
    var stack: Array<Int> = []
    for string in tokens {
        if "+ - * /".contains(where: { String($0) == string }) {
            let left = stack.last!
            stack.removeLast()
            let right = stack.last!
            stack.removeLast()
            var temp = 0
            switch string {
            case "+": temp = right + left
            case "-": temp = right - left
            case "*": temp = right * left
            case "/": temp = right / left
            default: break
            }
            stack.append(temp)
        }
        else{ stack.append(Int(string)!) }}return stack.first!
}
Copy the code