Swift Suffix Expression (Reverse Polish Notation) Conversion Calculation#
Background#
Recently, during the development of "Challenge 24 Points," I encountered a problem: how to calculate the result of commonly used mathematical expressions. For example, given the string 8 - (6 + 4 / 2 - 1) * 2, how can we compute the result and show the calculation process?
After researching online, I found that most resources handle it similarly to system calculators, where the result of the previous operation is computed when encountering the second operator. This approach does not apply to the problem I want to solve.
Further searching led me to the concepts of prefix expressions、infix expressions、and suffix expressions. The given string 8 - (6 + 4 / 2 - 1) * 2 is an infix expression. To compute the result, it can be converted to a prefix or suffix expression, and then the converted expression can be evaluated.
Here, we will convert the infix expression to a suffix expression and then calculate the result from the suffix expression. The steps are as follows.
Swift Infix Expression to Suffix Expression#
What are Infix and Suffix Expressions?#
First, let's understand what infix expressions and suffix expressions are:
- Infix Expression: This is a commonly used arithmetic representation method where operators are placed between operands, such as (a + b), hence the name infix expression.
- Suffix Expression: In this format, operators are written after their operands, such as (a, b, +), which is called a suffix expression, also known as reverse Polish notation.
Why Convert Infix Expressions to Suffix Expressions?#
Why convert simple infix expressions to suffix expressions? Because the simplicity of infix expressions makes them very complex for computers, which cannot compute them directly. In contrast, suffix expressions are a simpler and more understandable structure for computers. Therefore, when calculating common expressions, they should be converted to suffix expressions first.
How to Convert?#
Now let's look at how to convert an infix expression to a suffix expression. It is recommended to read through this once, understand it, and then try it on paper according to the principles to gain a better understanding.
Principle:
- Since Swift does not have a stack concept, we will use an array to implement it, simulating stack operations with array append and popLast.
- Declare two arrays to store numbers and operators respectively.
- Traverse the expression from left to right:
- If encountering a space, continue to the next character.
- If encountering a number, place it in the number array.
- If encountering ")", pop the last element from the operator array until encountering "(".
- If encountering an operator, compare the operator's precedence:
- If the last element in the operator array is "(", or the operator to be added is "(", do not compare precedence; directly add the operator to the operator array.
- If the precedence of the operator to be added is not greater than that of the last element in the operator array, pop the last element from the operator array into the number array until encountering an operator with lower precedence or "(".
- After completing the traversal of the expression, if the operator array is not empty, pop the elements from the operator array in reverse order into the number array.
- Finally, return the number array, which is the required suffix expression array.
The process is as follows:
Assuming we have an expression: 8 - (6 + 4 / 2 - 1) * 2, we can practice according to the steps above as follows:
// Initialize two arrays, the top for the number array and the bottom for the operator array
[]
[]
// The next character is "8", which is a number, directly place it in the number array
["8"]
[]
// The next character is "-", which is an operator. The operator array is empty, so no precedence comparison is needed; directly place it in the operator array
["8"]
["-"]
// The next character is "(", which is an operator. The element to be added is "(", so no precedence comparison is needed; "(" is directly placed in the operator array
["8"]
["-", "("]
// The next character is "6", which is a number, place it in the number array
["8", "6"]
["-", "("]
// The next character is "+", which is an operator. The last element in the operator array is "(", so no precedence comparison is needed; "+" is directly placed in the operator array
["8", "6"]
["-", "(", "+"]
// The next character is "4", which is a number, place it in the number array
["8", "6", "4"]
["-", "(", "+"]
// The next character is "/", which is an operator. "/" has higher precedence than the last element "+" in the operator array, so "/" is directly placed in the operator array
["8", "6", "4"]
["-", "(", "+", "/"]
// The next character is "2", which is a number, place it in the number array
["8", "6", "4", "2"]
["-", "(", "+", "/"]
// The next character is "-", which is an operator.
// "-" has lower precedence than the last element "/" in the operator array, so "/" is popped from the operator array and added to the number array.
// Comparing again, "-" has lower precedence than the last element "+" in the operator array, so "+" is popped from the operator array and added to the number array.
// Comparing again, the last element in the operator array is "(", so no precedence comparison is needed; "-" is placed in the operator array
["8", "6", "4", "2", "/", "+"]
["-", "(", "-"]
// The next character is "1", which is a number, place it in the number array
["8", "6", "4", "2", "/", "+", "1"]
["-", "(", "-"]
// The next character is ")", which is an operator. Pop the last element from the operator array until encountering "(", and remove "(" from the operator array
["8", "6", "4", "2", "/", "+", "1", "-"]
["-"]
// The next character is "*", which is an operator. "*" has higher precedence than the last element "-" in the operator array, so it is directly placed in the operator array
["8", "6", "4", "2", "/", "+", "1", "-"]
["-", "*"]
// Finally, pop the elements from the operator array in reverse order into the number array
["8", "6", "4", "2", "/", "+", "1", "-", "2", "*", "-"]
This part can be understood multiple times. After breaking down the logic step by step, we can write the implementation code as follows:
// Only consider single-digit numbers (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 {
// If it's a number, place it in the expression
suffixExpressionList.append(itemStr)
}
else {
if operatorExpressionList.count == 0 {
operatorExpressionList.append(itemStr)
}
else {
// It's an operator, including "+ - * / ( )"
if itemStr == ")" {
// When encountering ")", pop the operators from the array and append them to the expression until encountering "("
let temp: (l1: [String], l2: [String]) = handleAppendExpressionList(operatorExpressionList, suffixList: suffixExpressionList, isRightBracket: true)
operatorExpressionList = temp.l1
suffixExpressionList = temp.l2
}
else {
// Compare operator precedence * / is greater than + -
// If item is not greater than the last element in the current array, pop the last element until the precedence is greater than the last element, then add item
// If during comparison, encountering ( and item is not ), stop
let lastStr = operatorExpressionList.last
let isItemPriorityHigh = isFirstOperatorPriorityHigh(first: itemStr, second: lastStr!)
if isItemPriorityHigh || itemStr == "(" || lastStr == "(" {
// If the item operator is higher than last, directly push it onto the stack
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
}
// Logic to handle operator array to expression array
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 { // Only right brackets can eliminate left brackets
operatorExpressionList.append("(")
}
}
}
else {
lastStr = ""
}
} while ((lastStr != "(") && (lastStr != ""))
return (operatorExpressionList, suffixExpressionList)
}
// Only compare + - * /
func isFirstOperatorPriorityHigh(first: String, second: String) -> Bool {
let isFirst = isMultiplyOrDivideOperator(itemStr: first)
let isSecond = isMultiplyOrDivideOperator(itemStr: second)
if isFirst && !isSecond { // If first is * or / and second is not * or /, then first is higher than second
return true
}
return false
}
// Determine operator precedence
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)
Calculation of Suffix Expressions#
Principle of Suffix Expression Calculation#
The principle of calculating suffix expressions is as follows:
-
Traverse the array from left to right. When encountering an operator, take the two numbers a and b before the operator op, compute according to the logic a op b, and remove the three elements from the array. (Note that when removing, the method cannot be one by one; removing one will change the position of the array elements.)
-
Insert the result r into the array at the position of a before computation.
-
Repeat the traversal of the array according to the above logic until only one element remains in the array, which is the result.
The process is as follows:
Practice as follows:
// Initial
["8", "6", "4", "2", "/", "+", "1", "-", "2", "*", "-"]
// Traverse from left to right, the first symbol is "/", the two elements before "/" are "4" and "2", so we place the result of "4/2" in the array and remove "4", "2", "/"
["8", "6", "2.000000", "+", "1", "-", "2", "*", "-"]
// Traverse from left to right, the first symbol is "+", the two elements before "+" are "6" and "2.0", so we place the result of "6+2.0" in the array and remove "6", "2.0", "+"
["8", "8.000000", "1", "-", "2", "*", "-"]
// Traverse from left to right, the first symbol is "-", the two elements before "-" are "8.0" and "1", so we place the result of "8.0 - 1" in the array and remove "8.0", "1", "-"
["8", "7.000000", "2", "*", "-"]
// Traverse from left to right, the first symbol is "*", the two elements before "*" are "7.0" and "2", so we place the result of "7.0*2" in the array and remove "7.0", "2", "*"
["8", "14.000000", "-"]
// Traverse from left to right, the first symbol is "-", the two elements before "-" are "8" and "14.0", so we place the result of "8-14.0" in the array and remove "8", "14.0", "-"
// Finally, only one element remains -6.0, which is the final result
["-6.000000"]
// Finally, we get the result
8 - (6 + 4 / 2 - 1) * 2 = -6.0
The Calculation Code is as follows:#
// Calculation of Suffix Expressions
func calculatorExpressionList(_ expressionList: [String]) -> Double {
if expressionList.count == 1 {
return (expressionList.first as NSString?)?.doubleValue ?? 0.0
}
// The calculation logic is as follows:
// Traverse the array from left to right,
var targetList: [String] = expressionList
for index in 0..<expressionList.count {
let item = expressionList[index]
let isOp = isOperator(item)
// When encountering an operator, take the two numbers a and b before the operator op, compute according to the logic a op b
if isOp {
let a = expressionList[index - 2]
let b = expressionList[index - 1]
let r = calculator(a, item, b)
// Insert the result r into the array at the position of a before computation
targetList[index - 2] = r
// Remove the two elements that have been computed
targetList.removeSubrange(Range(NSRange(location: index-1, length: 2))!)
break
}
}
print(targetList)
// Repeat the traversal of the array according to the above logic until only one element remains, which is the result
return calculatorExpressionList(targetList)
}
// Calculation
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)
}
// Check if it is an operator
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)
Supplement:#
If you only want the result of the expression calculation without needing the process, you can directly use NSExpression to calculate the result of the expression. The code is as follows:
// Use NSExpression to calculate the result of the expression
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)
}
}
Summary#
Code link: https://github.com/mokong/ExpressionCalculator
Code effect:
