Swift 後綴表達式 (逆波蘭式) 轉換計算#
背景#
最近在開發《挑戰 24 點》的過程中遇到了個問題，即，如何計算常用數學表達式的結果，即，給定字符串8 - (6 + 4 / 2 - 1) * 2，怎麼計算得到結果，並且得到計算的過程。
網上查資料發現，大部分都是類似系統計算器的處理，在遇到第二個運算符時，就把前一步的操作結果計算出來。這樣的處理方式並不適用於筆者想要解決的問題。
進一步搜索後發現，前綴表達式、中綴表達式、後綴表達式的概念，給定的字符串8 - (6 + 4 / 2 - 1) * 2屬於中綴表達式，而想要計算機得出結果，可以轉為前綴表達式或者後綴表達式，然後再對轉換後的表達式進行計算。
這裡採用中綴表達式轉後綴表達式，然後計算後綴表達式得出結果，步驟如下。
Swift 中綴表達式轉後綴表達式#
什麼是中綴表達式、後綴表達式？#
- 中綴表達式: 是常用的算術表示方法，操作符處於操作數的中間，比如 (a + b)，即中綴形式，故而稱之為中綴表達式。
- 後綴表達式: 運算符寫在操作數之後，比如 (a, b, +)，稱之為後綴表達式，又名逆波蘭式。
為什麼要把中綴表達式轉為後綴表達式？#
為什麼要將簡單的中綴表達式轉為後綴表達式呢？因為中綴表達式的簡單對於計算機來說是非常複雜的，沒有辦法直接運算，而後綴表達式對於計算機而言是簡單易懂的結構。所以計算常見的表達式時，要轉為後綴表達式，然後運算。
怎麼轉？#
然後來看下，如何把中綴表達式轉為後綴表達式，這裡建議先看一遍，理解後，在本子上按照原理嘗試一遍，更能理解。
原理：
- 由於 Swift 中沒有棧的概念，所以採用數組的實現方式，用數組 append 模擬入棧，popLast 來模擬出棧。
- 聲明兩個數組，分別用於存儲數字和運算符
- 從左到右遍歷表達式，
- 遇到 " "，繼續遍歷下個字符
- 遇到數字則放入數字數組中
- 遇到 ")"，則把運算符數組中最後一個元素彈出，直到遇到 "(" 時停止。
- 遇到運算符，則比較運算符的優先級，
- 運算符數組中最後一個為 "(" 時，或者要放入的運算符為 "("，則不需要比較優先級，直接把要放入的運算符放入運算符數組中
- 如果要放入的運算符的優先級不大於運算符數組中最後一個的優先級，則把運算符數組中的最後一個彈出放入到數字數組中，直到遇到優先級比它低的時停止或者遇到 "(" 時停止。然後把運算符放入運算符數組中。
- 遍歷表達式完成後，如果運算符數組不為空，則把運算符數組中的元素倒序彈出，放入到數字數組中
- 最後返回數字數組，即所需要的後綴表達式的數組
流程如下：
假設現有一個表達式：8 - (6 + 4 / 2 - 1) * 2，按照上面的步驟實踐如下：
// 初始化兩個數組，上面為數字數組、下面為運算符數組
[]
[]
// 下個字符為"8"，是數字，直接放入數字數組中
["8"]
[]
// 下個字符為"-"，是運算符，運算符數組為空，故而不需要比較優先級，直接放入運算符數組中
["8"]
["-"]
// 下個字符為"("，是運算符，要放入的元素是"("，不需要比較優先級，"("直接放入運算符數組中
["8"]
["-", "("]
// 下個字符為"6"，是數字，放入數字數組中
["8", "6"]
["-", "("]
// 下個字符為"+"，是運算符，運算符數組中最後一個元素為"("，不需要比較優先級，"+"直接放入運算符數組中
["8", "6"]
["-", "(", "+"]
// 下個字符為"4"，是數字，放入數字數組中
["8", "6", "4"]
["-", "(", "+"]
// 下個字符為"/"，是運算符，"/"比運算符數組中最後一個元素"+"的優先級高，故而"/"直接放入運算符數組中
["8", "6", "4"]
["-", "(", "+", "/"]
// 下個字符為"2"，是數字，放入數字數組中
["8", "6", "4", "2"]
["-", "(", "+", "/"]
// 下個字符為"-"，是運算符，
// "-"比運算符數組中最後一個元素"/"的優先級低，故而"/"從運算符數組中彈出，添加到數字數組中。
// 再次比較"-"優先級不高於運算符數組中最後一個元素"+"，故而"+"從運算符數組中彈出，添加到數字數組中。
// 再次比較，運算符數組中最後一個元素為"("，故而不需要比較優先級，"-"放入運算符數組中
["8", "6", "4", "2", "/", "+"]
["-", "(", "-"]
// 下個字符為"1"，是數字，放入數字數組中
["8", "6", "4", "2", "/", "+", "1"]
["-", "(", "-"]
// 下個字符為")"，是運算符，把運算符數組中最後一個元素彈出，直到遇到"("時停止，且把"("從運算符數組中移出
["8", "6", "4", "2", "/", "+", "1", "-"]
["-"]
// 下個字符為"*"，是運算符，"*"的優先級比運算符數組中最後一個元素"-"的優先級高，故而直接放入運算符數組中
["8", "6", "4", "2", "/", "+", "1", "-"]
["-", "*"]
// 最後，把運算符數組中的元素倒序放入數字數組中
["8", "6", "4", "2", "/", "+", "1", "-", "2", "*", "-"]
這個地方可以多理解幾次，裡面的邏輯按步驟劃分之後，再來寫實現代碼，代碼實現如下：
// 只考慮0-9的數字，即單個數字的情況
func converExpressionToSuffixExpression(_ expressionStr: String) -> [String] {
var suffixExpressionList: [String] = []
var operatorExpressionList: [String] = []
for item in expressionStr {
let itemStr = String(item)
if itemStr == " " {
continue
}
print(suffixExpressionList)
print(operatorExpressionList)
print("\n")
if item.isNumber == true {
// 是數字則放入表達式中
suffixExpressionList.append(itemStr)
}
else {
if operatorExpressionList.count == 0 {
operatorExpressionList.append(itemStr)
}
else {
// 是運算符，包含"+ - * / ( )"
if itemStr == ")" {
// 遇到")"，則把數組中的運算符彈出，放入到表達式末尾，直到遇到"("停止
let temp: (l1: [String], l2: [String]) = handleAppendExpressionList(operatorExpressionList, suffixList: suffixExpressionList, isRightBracket: true)
operatorExpressionList = temp.l1
suffixExpressionList = temp.l2
}
else {
// 比較運算符的優先級 * / 大於 + -
// 如果 item 不大於當前數組裡最後一個元素，則數組裡最後一個元素彈出，直到優先級大於最後一個元素為止，item 加入
// 如果 item 比較中，遇到 ( 且，item 不是 )，則停止
let lastStr = operatorExpressionList.last
let isItemPriorityHigh = isFirstOperatorPriorityHigh(first: itemStr, second: lastStr!)
if isItemPriorityHigh || itemStr == "(" || lastStr == "(" {
// item運算符比 last 高，則直接入棧
operatorExpressionList.append(itemStr)
}
else {
let temp: (l1: [String], l2: [String]) = handleAppendExpressionList(operatorExpressionList, suffixList: suffixExpressionList, isRightBracket: false)
operatorExpressionList = temp.l1
suffixExpressionList = temp.l2
operatorExpressionList.append(itemStr)
}
}
}
}
}
if operatorExpressionList.count > 0 {
repeat {
if let tempLastStr = operatorExpressionList.popLast() {
suffixExpressionList.append(tempLastStr)
}
} while (operatorExpressionList.count > 0)
}
return suffixExpressionList
}
// 處理符號數組到表達式數組邏輯
func handleAppendExpressionList(_ operatorList: [String], suffixList: [String], isRightBracket: Bool) -> ([String], [String]) {
var operatorExpressionList = operatorList
var suffixExpressionList = suffixList
var lastStr = operatorExpressionList.last
repeat {
let tempLastStr = operatorExpressionList.popLast()
if tempLastStr != nil {
lastStr = tempLastStr!
if lastStr != "(" {
suffixExpressionList.append(tempLastStr!)
}
else {
if isRightBracket != true { // 只有右括號能消除左括號
operatorExpressionList.append("(")
}
}
}
else {
lastStr = ""
}
} while ((lastStr != "(") && (lastStr != ""))
return (operatorExpressionList, suffixExpressionList)
}
// 只比較 + - * /
func isFirstOperatorPriorityHigh(first: String, second: String) -> Bool {
let isFirst = isMultiplyOrDivideOperator(itemStr: first)
let isSecond = isMultiplyOrDivideOperator(itemStr: second)
if isFirst && !isSecond { // 如果 first 是 * 或者 /，且second 不是 * 或者 /， 則 first高於 second
return true
}
return false
}
// 判斷運算符優先級
func isMultiplyOrDivideOperator(itemStr: String) -> Bool {
if itemStr == "*" ||
itemStr == "x" ||
itemStr == "×" ||
itemStr == "X" ||
itemStr == "/" ||
itemStr == "÷"{
return true
}
return false
}
//let normalStr = "(8 x (7 - (4 * 1)))"
//let normalStr = "8 - 6 / 4 + 1"
//let normalStr = "8 - (6 / 4 + 1)"
//let normalStr = "8 - 6 + 4 * 1"
let normalStr = "8 - (6 + 4 / 2 - 1) * 2"
let expressionList = converExpressionToSuffixExpression(normalStr)
print(expressionList)
後綴表達式的計算#
後綴表達式計算的原理#
後綴表達式計算的原理如下：
-
從左到右遍歷數組，遇到運算符後，把運算符 op 前面的兩個數字 a, b 取出，按照 a op b 的邏輯計算，並把三個元素從數組中移除。(這裡需要注意移除時的方法，不能一個個移除，移除一個後，數組元素的位置就發生了改變）
-
將 運算結果 r 插入到數組中計算前 a 的位置
-
重複遍歷數組，按照上面邏輯計算，直到數組中只有一個元素即結果為止
流程如下：
實踐如下：
// 初始
["8", "6", "4", "2", "/", "+", "1", "-", "2", "*", "-"]
// 從左到右遍歷，第一個符號是"/"，"/"前面的兩個元素是"4"和"2"，故而把"4/2"的結果放入數組中，把"4", "2", "/"三個元素移出
["8", "6", "2.000000", "+", "1", "-", "2", "*", "-"]
// 從左到右遍歷，第一個符號是"+"，"+"前面的兩個元素是"6"和"2.0"，故而把"6+2.0"的結果放入數組中，把"6", "2.0", "+"三個元素移出
["8", "8.000000", "1", "-", "2", "*", "-"]
// 從左到右遍歷，第一個符號是"-"，"/"前面的兩個元素是"8.0"和"1"，故而把"8.0 - 1"的結果放入數組中，把"8.0", "1", "-"三個元素移出
["8", "7.000000", "2", "*", "-"]
// 從左到右遍歷，第一個符號是"*"，"*"前面的兩個元素是"7.0"和"2"，故而把"7.0*2"的結果放入數組中，把"7.0", "2", "*"三個元素移出
["8", "14.000000", "-"]
// 從左到右遍歷，第一個符號是"-"，"-"前面的兩個元素是"8"和"14.0"，故而把"8-14.0"的結果放入數組中，把"8", "14.0", "-"三個元素移出
// 最後只剩一個元素-6.0，即最終運算結果
["-6.000000"]
// 最後得到結果
8 - (6 + 4 / 2 - 1) * 2 = -6.0
計算代碼如下：#
// 後綴表達式的計算
func calculatorExpressionList(_ expressionList: [String]) -> Double {
if expressionList.count == 1 {
return (expressionList.first as NSString?)?.doubleValue ?? 0.0
}
// 計算邏輯如下：
// 從左到右遍歷數組，
var targetList: [String] = expressionList
for index in 0..<expressionList.count {
let item = expressionList[index]
let isOp = isOperator(item)
// 遇到運算符後，把運算符 op 前面的兩個數字a, b取出，按照 a op b 的邏輯計算
if isOp {
let a = expressionList[index - 2]
let b = expressionList[index - 1]
let r = calculator(a, item, b)
// 將 運算結果r 插入到數組中計算前 a 的位置
targetList[index - 2] = r
// 移出運算過的那兩個元素
targetList.removeSubrange(Range(NSRange(location: index-1, length: 2))!)
break
}
}
print(targetList)
// 重複遍歷數組，按照上面邏輯計算，直到數組中只有一個元素即結果為止
return calculatorExpressionList(targetList)
}
// 計算
func calculator(_ a: String, _ op: String, _ b: String) -> String {
var result: Double = 0.0
let aValue = (a as NSString).doubleValue
let bValue = (b as NSString).doubleValue
switch op {
case "+":
result = aValue + bValue
case "-":
result = aValue - bValue
case "*", "×", "x", "X":
result = aValue * bValue
case "/", "÷":
if bValue != 0.0 {
result = aValue / bValue
}
default:
break
}
return String(format: "%f", result)
}
// 是否是運算符
func isOperator(_ str: String) -> Bool {
var result = false
let isMultipleOrDivide = isMultiplyOrDivideOperator(itemStr: str)
if isMultipleOrDivide == false {
if str == "+" ||
str == "-" {
result = true
}
}
else {
result = isMultipleOrDivide
}
return result
}
// let normalStr = "(8 x (7 - (4 * 1)))"
// let normalStr = "8 - 6 / 4 + 1"
// let normalStr = "8 - (6 / 4 + 1)"
let normalStr = "8 - 6 + 4 * 1"
let expressionList = converExpressionToSuffixExpression(normalStr)
print(expressionList)
//let expressionList = converExpressionToSuffixExpression("8 - 6 / 4 + 1")
//let expressionList = converExpressionToSuffixExpression("8 - (6 / 4 + 1)")
//let expressionList = converExpressionToSuffixExpression("8 - 6 + 4 * 1")
let result = calculatorExpressionList(expressionList)
print(normalStr, "=", result)
補充：#
如果只想要表達式的計算結果，不需要使用過程，則可以直接使用 NSExpression計算表達式的結果，代碼如下：
// 使用 NSExpression 計算表達式的結果
fileprivate func nsexpressionCalculate() {
let expressionStr = "2 + 3 * (5 - 1)"
let formatExpressionStr = expressionStr.replacingOccurrences(of: " ", with: "")
let expression = NSExpression(format: formatExpressionStr)
if let result = expression.expressionValue(with: nil, context: nil) as? NSNumber {
print(result)
}
}
總結#
代碼鏈接：https://github.com/mokong/ExpressionCalculator
代碼效果：
