LeetCode习题：计算器
2021-03-25 本文已影响0人
华子的学习之路
题目描述：给定一个包含正整数、加(+)、减(-)、乘(*)、除(/)的算数表达式(括号除外)，计算其结果。表达式仅包含非负整数，+，- ，*，/ 四种运算符和空格 。 整数除法仅保留整数部分。
示例：
例1：
输入: "3+2*2"
输出: 7
例2：
输入: " 3/2 "
输出: 1
例3：
输入: " 3+5 / 2 "
输出: 5
解题思路：双栈计算。创建两个栈结构，分别用于保存数字和运算符，遍历字符串时，遇到运算符，将当前运算符与运算符栈的栈顶进行优先级比较，如果栈顶运算符优先级低于当前运算符，将数字和当前运算符直接入栈，如果栈顶运算符优先级高于或者等于当前运算符，取出数字栈和运算符栈栈顶数据，结合num保存的临时数据进行运算，运算结果依然保存到num，取出运算符栈新的栈顶数据，进行以上逻辑比较及运算或者直接入栈。最后依次取出两个栈中的数据进行运算，返回运算结果。
特别注意：由于一次计算后，紧接着从运算符栈出栈了一个数据，如果比较结果是无需继续计算，直接入栈，当该数据不为空时，记得将其重新入栈。
解题开发语言：Swift
struct ArrayStack {
private var listData: [String]!
private var n: Int!
private var count: Int!
// 栈顶元素
public var stackTop: String? {
if count == 0 {
return nil
}
return listData[count-1]
}
init(num: Int) {
listData = [String](repeating: "", count: num)
n = num
count = 0
}
// 入栈
public mutating func push(item: String) -> Bool {
if count == n {
resize()
}
listData[count] = item
count += 1
return true
}
// 出栈
public mutating func pop() -> String? {
if count == 0 {
return nil
}
let val = listData[count-1]
count -= 1
return val
}
// 是否为空
public var isEmpty: Bool {
return listData.isEmpty
}
// 清空栈
public mutating func clear() {
listData.removeAll()
count = 0
}
// 扩充
private mutating func resize() {
var newAry = [String](repeating: "", count: n * 2)
let range = newAry.startIndex..<newAry.index(newAry.startIndex, offsetBy: n)
newAry.replaceSubrange(range, with: listData)
listData = newAry
n = n * 2
}
}
class Solution {
let numbers = ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"]
let operators = ["+", "-", "*", "/"]
func calculate(_ s: String) -> Int {
// 数字栈
var numberStack = ArrayStack(num:4)
// 运算符栈
var operatorStack = ArrayStack(num:2)
// 保存多位数
var num = ""
for item in s {
let char = String(item)
if (numbers.contains(char)) {
num += char
} else if (operators.contains(char)) {
var top = operatorStack.stackTop
if (top == nil) {
numberStack.push(item: num)
num = ""
operatorStack.push(item: char)
} else {
var judgeResult = judgeOperatorLevel(top!, char)
if (!judgeResult) {
numberStack.push(item: num)
num = ""
operatorStack.push(item: char)
} else {
top = operatorStack.pop()
while(judgeResult) {
let number = numberStack.pop()
num = getOperatorResult(num1: number!, num2: num, priority: top!)
top = operatorStack.pop()
if (top != nil) {
judgeResult = judgeOperatorLevel(top!, char)
} else {
judgeResult = false
}
}
numberStack.push(item: num)
num = ""
// 最后一次出栈的运算符不为空，重新入栈
if top != nil {
operatorStack.push(item: top!)
}
operatorStack.push(item: char)
}
}
}
}
var e = operatorStack.pop()
while e != nil {
let d = numberStack.pop()
num = getOperatorResult(num1: d!, num2: num, priority: e!)
e = operatorStack.pop()
}
return Int(num) ?? 0
}
// 判断运算符优先级(前者是否比后者优先级高)
func judgeOperatorLevel(_ a: String, _ b: String) -> Bool {
let aLevel = getOperatorLevel(a)
let bLevel = getOperatorLevel(b)
return aLevel >= bLevel
}
func getOperatorLevel(_ c: String) -> Int {
if (c == "+" || c == "-") {
return 1
} else if (c == "*" || c == "/") {
return 2
} else {
return 0
}
}
// 运算
func getOperatorResult(num1: String, num2: String, priority: String) -> String {
let val1 = Int(num1) ?? 0
let val2 = Int(num2) ?? 0
var result: Int?
switch priority {
case "+":
result = val1 + val2
break
case "-":
result = val1 - val2
break
case "*":
result = val1 * val2
break
case "/":
result = val1 / val2
break
default:
break
}
return String(result ?? 0)
}
}
