[Swift]LeetCode150.逆波兰表达式求值|EvaluateReversePolishNotation

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Note:

Division between two integers should truncate toward zero.
The given RPN expression is always valid. That means the expression would always evaluate to a result and there won't be any divide by zero operation.

Example 1:

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

Example 2:

Input: ["4", "13", "5", "/", "+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Example 3:

Input: ["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
= 17 + 5
= 22

根据逆波兰表示法，求表达式的值。

有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例 1：

输入: ["2", "1", "+", "3", "*"]
输出: 9
解释: ((2 + 1) * 3) = 9

示例 2：

输入: ["4", "13", "5", "/", "+"]
输出: 6
解释: (4 + (13 / 5)) = 6

示例 3：

输入: ["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

52ms

 1 class Solution {
 2     func evalRPN(_ tokens: [String]) -> Int {
 3         var intStack = [Int]()
 4         for t in tokens {
 5             switch t {
 6                 case "+":
 7                     guard let a = intStack.popLast(), let b = intStack.popLast() else {return -1}
 8                     intStack.append(a+b)
 9                 case "-":
10                     guard let a = intStack.popLast(), let b = intStack.popLast() else {return -1}
11                     intStack.append(b-a)
12                 case "*":
13                     guard let a = intStack.popLast(), let b = intStack.popLast() else {return -1}
14                     intStack.append(b*a)
15                 case "/":
16                     guard let a = intStack.popLast(), let b = intStack.popLast() else {return -1}
17                     intStack.append(b/a)
18                 default:
19                     guard let n = Int(t) else {return -1}
20                     intStack.append(n)
21             }
22         }
23         return intStack.last!
24     }
25 }

60ms

 1 class Stack<T> {
 2     var arr = [T]()
 3 
 4     func insert(_ v: T) {
 5         arr.append(v)
 6     }
 7 
 8     func dequeue() -> T? {
 9         if arr.count == 0 { return nil }
10         return arr.removeLast()
11     }
12 }
13 
14 class Solution {
15     func evalRPN(_ tokens: [String]) -> Int {
16         let stack = Stack<Int>()
17         for item in tokens {
18             if let numericItem = Int(item) {
19                 stack.insert(numericItem)
20             } else {
21                 if let rhs = stack.dequeue(), let lhs = stack.dequeue() {
22                     switch item {
23                     case "+":
24                         stack.insert(lhs + rhs)
25                     case "-":
26                         stack.insert(lhs - rhs)
27                     case "*":
28                         stack.insert(lhs * rhs)
29                     case "/":
30                         stack.insert(lhs / rhs)
31                     default:
32                         break
33                     }
34                 } else {
35                     fatalError("wrong rpn")
36                 }
37             }
38         }
39         return stack.dequeue()!
40     }
41 }

64ms

 1 class Solution {
 2     private struct Stack<Type> {
 3         var arr = [Type]()
 4         mutating func push(_ e: Type) {
 5             arr.insert(e, at: arr.count)
 6         }
 7         mutating func pop() -> Type? {
 8             if arr.count > 0 {
 9                 return arr.remove(at: arr.count-1)
10             }
11             return nil
12         }
13         
14         var isEmpty: Bool {
15             return arr.count <= 0
16         }
17     }
18     
19     func evalRPN(_ tokens: [String]) -> Int {
20         var stack = Stack<Int>()
21         for str in tokens {
22             if let num = Int(str) {
23                 stack.push(num)
24             } else {
25                 let op2 = stack.pop()!
26                 let op1 = stack.pop()!
27                 var ret = 0
28                 switch str {
29                 case "+":
30                     ret = op1 + op2
31                 case "-":
32                     ret = op1 - op2
33                 case "*":
34                     ret = op1 * op2
35                 case "/":
36                     ret = op1 / op2
37                 default:
38                     break
39                 }
40                 stack.push(ret)
41             }
42         }
43         return stack.pop()!
44     }
45 }

100ms

 1 class Solution {
 2     enum Operation: String {
 3         case plus = "+"
 4         case minus = "-"
 5         case divive = "/"
 6         case mutiple = "*"
 7         
 8         func comput(_ num1: Int, _ num2: Int) -> Int {
 9             switch self {
10             case .plus:
11                 return num1 + num2
12             case .minus:
13                 return num1 - num2
14             case .divive:
15                 return num1 / num2
16             case .mutiple:
17                 return num1 * num2
18             }
19         }
20     }
21     
22     func evalRPN(_ tokens: [String]) -> Int {
23         var opertationNumer: [Int] = []
24         
25         tokens.forEach { (token) in
26             if let num = Int(token) {
27                 opertationNumer.append(num)
28             } else if let operation = Operation(rawValue: token) {
29                 if let num2 = opertationNumer.popLast(),
30                     let num1 = opertationNumer.popLast() {
31                     let res = operation.comput(num1, num2)
32                     opertationNumer.append(res)
33                 }
34             }
35         }
36         return opertationNumer.popLast()!
37     }
38 }

116ms

 1 class Solution {
 2     func evalRPN(_ tokens: [String]) -> Int {
 3         var stack = [Int]()
 4         
 5         for char in tokens {
 6             switch char {
 7                 case "+":
 8                     stack.append(stack.remove(at: stack.count - 2) + stack.removeLast())
 9                 case "-":
10                     stack.append(stack.remove(at: stack.count - 2) - stack.removeLast())
11                 case "*":
12                     stack.append(stack.remove(at: stack.count - 2) * stack.removeLast())
13                 case "/":
14                     stack.append(stack.remove(at: stack.count - 2) / stack.removeLast())
15                 default:
16                     stack.append(Int(String(char))!)
17             }
18         }
19         
20         return stack.first!
21     }
22 }

120ms

 1 class Solution {
 2     func evalRPN(_ tokens: [String]) -> Int {
 3         var stack = [Int]()
 4         
 5         for token in tokens {
 6             if let num = Int(token) {
 7                 stack.append(num)
 8             } else {
 9                 let post = stack.removeLast()
10                 let prev = stack.removeLast()
11                 
12                 stack.append(operate(prev, post, token))
13             }
14         }
15         
16         return stack.first ?? 0
17     }
18     
19     func operate(_ prev: Int, _ post: Int, _ token: String) -> Int{
20         switch token {
21             case "+":
22                 return prev + post
23             case "-":
24                 return prev - post
25             case "*":
26                 return prev * post
27             default:
28                 return prev / post
29        }
30     }
31 }

124ms

 1 class Solution {
 2     func evalRPN(_ tokens: [String]) -> Int {
 3 
 4         var stack = [String]()
 5         
 6         for (_ , str) in tokens.enumerated() {
 7             if str != "+" && str != "-" && str != "*" && str != "/" {
 8                 stack.append(str)
 9             } else {
10                 let postStr = stack.removeLast()
11                 let preStr = stack.removeLast()
12                 
13                 var res = 0
14                 if str == "+" {
15                     res = Int(preStr)! + Int(postStr)!
16                 } else if str == "-" {
17                     res = Int(preStr)! - Int(postStr)!
18                 } else if str == "*" {
19                     res = Int(preStr)! * Int(postStr)!
20                 } else {
21                     res = Int(preStr)! / Int(postStr)!
22                 }
23 
24                 stack.append(String(res))
25             }
26         }
27         
28         let val = stack.removeLast()
29         return Int(val)!
30     }
31 }

132ms

 1 class Solution {
 2     func evalRPN(_ tokens: [String]) -> Int {
 3         guard tokens.count > 0 else { return 0 }
 4         let operators = Set<String>(["+", "-", "*", "/"])
 5         var stack = [String]()
 6         for token in tokens {
 7             if operators.contains(token) {
 8                 let b = Int(stack.removeLast())!
 9                 let a = Int(stack.removeLast())!
10                 var res = 0
11                 switch token {
12                 case "+":
13                     res = a + b
14                     break
15                 case "-":
16                     res = a - b
17                     break
18                 case "*":
19                     res = a * b
20                     break
21                 case "/":
22                     res = a / b
23                     break
24                 default:
25                     break
26                 }
27                 stack.append(String(res))
28             } else {
29                 stack.append(token)
30             }
31         }
32         return Int(stack[0])!
33     }
34 }

148ms

  1 class Solution {
  2     enum Operator: String {
  3         case plus = "+"
  4         case minus = "-"
  5         case multiplication = "*"
  6         case division = "/"
  7 
  8         func evaluate(_ num1: Int, _ num2: Int) -> Int {
  9             let expression = self.expression()
 10             return expression(num1, num2)
 11         }
 12 
 13         func expression() -> ((Int, Int) -> Int) {
 14             switch self {
 15                 case .plus:
 16                     return { (a, b) in return (a + b) }
 17                 case .minus:
 18                     return { (a, b) in return (a - b) }
 19                 case .multiplication:
 20                     return { (a, b) in return (a * b) }
 21                 case .division:
 22                     return { (a, b) in return (a / b) }
 23             }
 24         }
 25     }
 26 
 27     func evalRPN(_ tokens: [String]) -> Int {
 28         let resultStack = Stack<Int>()
 29 
 30         for token in tokens {
 31             if let operatorValue = makeOperator(token) {
 32                 if let num1 = resultStack.pop(), let num2 = resultStack.pop() {
 33                     let result = operatorValue.evaluate(num2, num1)
 34                     resultStack.push(result)
 35                 } else {
 36                     assertionFailure("input tokens are not valid")
 37                     return 0
 38                 }
 39             } else if let integerValue = makeInteger(token) {
 40                 resultStack.push(integerValue)
 41             } else {
 42                 assertionFailure("input token is not valid")
 43                 return 0
 44             }
 45         }
 46 
 47         if let result = resultStack.pop() {
 48             return result
 49         } else {
 50             assertionFailure("input tokens are not in correct format")
 51             return 0
 52         }
 53     }
 54 
 55     func makeInteger(_ str: String) -> Int? {
 56         return Int(str)
 57     }
 58 
 59     func makeOperator(_ str: String) -> Operator? {
 60         return Operator(rawValue: str)
 61     }
 62 }
 63 
 64 public class Stack<T> {
 65 
 66     class Node {
 67         let value: T
 68         var next: Node?
 69 
 70         init(value: T, next: Node? = nil) {
 71             self.value = value
 72             self.next = next
 73         }
 74     }
 75 
 76     private var top: Node? = nil
 77     public private(set) var count: Int = 0
 78 
 79     public func push(_ value: T) {
 80         let node = Node(value: value)
 81         node.next = top
 82         top = node
 83         count += 1
 84     }
 85 
 86     @discardableResult
 87     public func pop() -> T? {
 88         let value = top?.value
 89         top = top?.next
 90         count -= 1
 91         return value
 92     }
 93 
 94     func printDescription() {
 95         var currentNode = top
 96         while let node = currentNode {
 97             print("[\(node.value)]", terminator: "->")
 98             currentNode = currentNode?.next
 99         }
100         print("[]")
101     }
102 }