Swift后缀表达式(逆波兰式)转换计算

2022-01-06

Swift后缀表达式(逆波兰式)转换计算

背景

最近在开发《挑战24点》的过程中遇到了一个问题，即，如何计算常用数学表达式的结果，即，给定字符串8 - (6 + 4 / 2 - 1) * 2，怎么计算得到结果，并且得到计算的过程。

网上查资料发现，大部分都是类似系统计算器的处理，在遇到第二个运算符时，就把前一步的操作结果计算出来。这样的处理方式并不适用于笔者想要解决的问题。

进一步搜索后发现，前缀表达式、中缀表达式、后缀表达式的概念，给定的字符串8 - (6 + 4 / 2 - 1) * 2属于中缀表达式，而想要计算机得出结果，可以转为前缀表达式或者后缀表达式，然后再对转换后的表达式进行计算。

这里采用中缀表达式转后缀表达式，然后计算后缀表达式得出结果，步骤如下。

Swift 中缀表达式转后缀表达式

什么是中缀表达式、后缀表达式？

首先理解中缀表达式和后缀表达式分别是什么？

中缀表达式: 是常用的算术表示方法，操作符处于操作数的中间，比如 (a + b)，即中缀形式，故而称之为中缀表达式。
后缀表达式: 运算符写在操作数之后，比如 (a, b, +)，称之为后缀表达式，又名逆波兰式。

为什么要把中缀表达式转为后缀表达式？

为什么要将简单的中缀表达式转为后缀表达式呢？因为中缀表达式的简单对于计算机来说是非常复杂的，没有办法直接运算，而后缀表达式对于计算机而言是简单易懂的结构。所以计算常见的表达式时，要转为后缀表达式，然后运算。

怎么转？

然后来看下，如何把中缀表达式转为后缀表达式，这里建议先看一遍，理解后，在本子上按照原理尝试一遍，更能理解。
原理：

由于 Swift 中没有栈的概念，所以采用数组的实现方式，用数组 append 模拟入栈，popLast 来模拟出栈。
声明两个数组，分别用于存储数字和运算符
从左到右遍历表达式，
1. 遇到” “，继续遍历下一个字符
2. 遇到数字则放入数字数组中
3. 遇到”)”，则把运算符数组中最后一个元素弹出，直到遇到”(“时停止。
4. 遇到运算符，则比较运算符的优先级，
  1. 运算符数组中最后一个为”(“时，或者要放入的运算符为”(“，则不需要比较优先级，直接把要放入的运算符放入运算符数组中
  2. 如果要放入的运算符的优先级不大于运算符数组中最后一个的优先级，则把运算符数组中的最后一个弹出放入到数字数组中，直到遇到优先级比它低的时停止或者遇到”(“时停止。然后把运算符放入运算符数组中。
遍历表达式完成后，如果运算符数组不为空，则把运算符数组中的元素倒序弹出，放入到数字数组中
最后返回数字数组，即所需要的后缀表达式的数组

流程如下：

算术表达式转后缀表达式.png

假设现有一个表达式：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 的位置
重复遍历数组，按照上面逻辑计算，直到数组中只有一个元素即结果为止

流程如下：

后缀表达式计算.png

实践如下：


// 初始
["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)
    }
}