Swift Suffix Expression (Reverse Polish Notation) Conversion Calculation#
Background#
Recently, while developing "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 obtain 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 revealed 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 calculated.
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?
- Infix expression: This is a common arithmetic representation method where the operator is placed between the operands, such as (a + b), hence it is called an infix expression.
- Suffix expression: The operator is written after the 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 simple and understandable structure for computers. Therefore, when calculating common expressions, they should be converted to suffix expressions before computation.
How to Convert?#
Now let's look at how to convert infix expressions to suffix expressions. It is recommended to read through this once to understand it, and then try it on paper according to the principles for better comprehension.
Principle:
- Since Swift does not have the concept of a stack, we will use an array to implement it, simulating push with array append and pop with popLast.
- Declare two arrays to store numbers and operators respectively.
- Traverse the expression from left to right:
- When encountering a " ", continue to the next character.
- When encountering a number, place it in the number array.
- When encountering ")", pop the last element from the operator array until encountering "(".
- When encountering an operator, compare the operator's precedence:
- If the last element in the operator array is "(", or the operator to be placed is "(", there is no need to compare precedence; simply place the operator in the operator array.
- If the precedence of the operator to be placed 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 traversing 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, 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 there is no need to compare precedence; directly place it in the operator array
["8"]
["-"]
// The next character is "(", which is an operator. The element to be placed is "(", so there is no need to compare precedence; "(" 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 there is no need to compare precedence; "+" 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 there is no need to compare precedence; "-" 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 into steps, 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 place them at the end of 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 from the array 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
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 the 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 a right bracket can eliminate a left bracket
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 the method of removal; you cannot remove them one by one, as removing one will change the position of the array elements.)
-
Insert the result r into the array at the position of a before calculation.
-
Repeat the traversal of the array according to the above logic until only one element, which is the result, remains in the array.
The process is as follows:
Practicing 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", "/" three elements
["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", "+" three elements
["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", "-" three elements
["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", "*" three elements
["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", "-" three elements
// Finally, only one element -6.0 remains, which is the final calculation 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, and 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 calculation
targetList[index - 2] = r
// Remove the two elements that have been calculated
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:
