Swiftサフィックス表現（逆ポーランド記法）変換計算

Swift の後置記法（逆ポーランド記法）変換計算#

背景#

最近『24 点チャレンジ』の開発中に、一般的な数学式の結果を計算する方法についての問題に直面しました。具体的には、与えられた文字列8 - (6 + 4 / 2 - 1) * 2から結果を計算し、その計算過程を得る方法です。

インターネットで調査したところ、大部分はシステム計算機の処理に類似しており、2 番目の演算子に遭遇すると、前の操作結果を計算します。このような処理方法は、私が解決したい問題には適していませんでした。

さらに検索したところ、前置記法、中置記法、後置記法の概念を発見しました。与えられた文字列8 - (6 + 4 / 2 - 1) * 2は中置記法に属し、コンピュータが結果を得るためには、前置記法または後置記法に変換し、その後変換された式を計算する必要があります。

ここでは中置記法を後置記法に変換し、その後後置記法を計算して結果を得る手順を示します。

Swift 中置記法から後置記法への変換#

中置記法と後置記法とは？#

まず、中置記法と後置記法のそれぞれの定義を理解しましょう。

中置記法: 一般的な算術表現方法で、演算子がオペランドの間に位置します。例えば (a + b) のように、中置形式と呼ばれます。
後置記法: 演算子がオペランドの後に書かれます。例えば (a, b, +) のように、後置記法または逆ポーランド記法と呼ばれます。

なぜ中置記法を後置記法に変換するのか？#

なぜ単純な中置記法を後置記法に変換する必要があるのでしょうか？中置記法はコンピュータにとって非常に複雑で、直接計算することができません。一方、後置記法はコンピュータにとって理解しやすい構造です。したがって、一般的な式を計算する際には後置記法に変換し、その後計算を行います。

どうやって変換するのか？#

次に、中置記法を後置記法に変換する方法を見ていきましょう。まずは一度見て理解し、その後原理に従ってノートに試してみることをお勧めします。
原理：

Swift にはスタックの概念がないため、配列を使用して実装します。配列の append を使用してスタックに入れ、popLast を使用してスタックから出します。
数字と演算子をそれぞれ格納するための 2 つの配列を宣言します。
左から右に式を走査します。
1. " " に遭遇した場合、次の文字を走査し続けます。
2. 数字に遭遇した場合、数字配列に追加します。
3. ")" に遭遇した場合、演算子配列の最後の要素をポップし、"(" に遭遇するまで続けます。
4. 演算子に遭遇した場合、演算子の優先順位を比較します。
  1. 演算子配列の最後の要素が "(" の場合、または追加する演算子が "(" の場合、優先順位を比較する必要はなく、直接演算子を演算子配列に追加します。
  2. 追加する演算子の優先順位が演算子配列の最後の優先順位以下の場合、演算子配列の最後の要素をポップして数字配列に追加し、優先順位が低いものに遭遇するまで、または "(" に遭遇するまで続けます。その後、演算子を演算子配列に追加します。
式の走査が完了した後、演算子配列が空でない場合、演算子配列の要素を逆順にポップして数字配列に追加します。
最後に数字配列を返します。これが必要な後置記法の配列です。

プロセスは以下の通りです：

算術表現を後置記法に変換.png

仮に次の式があるとします：8 - (6 + 4 / 2 - 1) * 2。上記の手順に従って実践すると、以下のようになります：


// 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 の前の 2 つの数字 a, b を取り出し、a op b の論理で計算し、3 つの要素を配列から削除します。（ここで注意が必要なのは、削除する際の方法で、1 つずつ削除するのではなく、1 つ削除すると配列の要素の位置が変わるためです）
計算結果 r を配列に挿入し、a の位置に置きます。
配列を再度走査し、上記の論理で計算を繰り返し、配列に 1 つの要素（結果）だけが残るまで続けます。

プロセスは以下の通りです：

後置記法計算.png

実践は以下の通りです：


// 初期
["8", "6", "4", "2", "/", "+", "1", "-", "2", "*", "-"]

// 左から右に走査し、最初の演算子は"/"で、"/"の前の2つの要素は"4"と"2"です。したがって、"4/2"の結果を配列に入れ、"4", "2", "/"の3つの要素を削除します。
["8", "6", "2.000000", "+", "1", "-", "2", "*", "-"]

// 左から右に走査し、最初の演算子は"+"で、"+"の前の2つの要素は"6"と"2.0"です。したがって、"6+2.0"の結果を配列に入れ、"6", "2.0", "+"の3つの要素を削除します。
["8", "8.000000", "1", "-", "2", "*", "-"]

// 左から右に走査し、最初の演算子は"-"で、"-"の前の2つの要素は"8.0"と"1"です。したがって、"8.0 - 1"の結果を配列に入れ、"8.0", "1", "-"の3つの要素を削除します。
["8", "7.000000", "2", "*", "-"]

// 左から右に走査し、最初の演算子は"*"で、"*"の前の2つの要素は"7.0"と"2"です。したがって、"7.0*2"の結果を配列に入れ、"7.0", "2", "*"の3つの要素を削除します。
["8", "14.000000", "-"]

// 左から右に走査し、最初の演算子は"-"で、"-"の前の2つの要素は"8"と"14.0"です。したがって、"8-14.0"の結果を配列に入れ、"8", "14.0", "-"の3つの要素を削除します。
// 最後に残る要素は-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の前の2つの数字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
            // 演算した2つの要素を削除します
            targetList.removeSubrange(Range(NSRange(location: index-1, length: 2))!)
            break
        }
    }

    print(targetList)
    // 配列を再度走査し、上記の論理で計算を繰り返し、配列に1つの要素（結果）だけが残るまで続けます
    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)
    }
}

まとめ#

swift_中置記法計算.png

コードリンク：https://github.com/mokong/ExpressionCalculator

コードの効果：

今是昨非