这是奔跑的键盘侠的第200篇文章
作者|我是奔跑的键盘侠
来源|奔跑的键盘侠（ID：runningkeyboardhero）
转载请联系授权
编写一个函数，要求能够实现字符串表达式的四则运算，并支持括号优先级的特性，要求：必须使用自己的算法实现表达式拆解。
这道题目算是编程领域老生常谈的题目，而且也是计算器实现的基本算法。但是对应业余选手来讲，还是要费点脑力值的。话说当年六级认证时，有遭遇这道题目，绞尽脑汁，那会网上没有什么代码参考，有的倒是各种算法说明，看得眼花缭乱，特别是这个括号相关的种种……
1
四则运算中括号的常见处理算法
- 递归求解法：递归求解法是最普遍、最自然的方法之一。它的思路是逐层拆分表达式并递归求解。具体来说，对于一个包含括号的表达式，首先将最内层的括号表达式拆分出来，然后递归地求解这个括号表达式。将求解结果带回原表达式中，继续拆分和求解直到所有的括号被去除。
- 栈处理法：栈处理法是另一种常见的方法。它的基本思路是用两个栈（一个操作数栈和一个操作符栈）来实现计算。遇到数字时将其压入操作数栈，遇到算符时将其压入操作符栈。当遇到右括号时，从操作数栈中弹出两个数，从操作符栈中弹出对应的算符进行运算，将结果压入操作数栈中。重复此过程，直到左括号被弹出为止。
- 中缀表达式转后缀表达式：中缀表达式转后缀表达式也是一种常用的处理方法。具体来说，该算法将中缀表达式转换为后缀表达式，再使用后缀表达式求解。转换过程中需要借助一个栈来实现。遇到数字时直接输出，遇到算符时将其压入栈中。如果栈顶元素是同级或更高优先级的算符，则弹出栈顶元素并输出，重复此过程直到栈为空或者栈顶元素优先级低于当前算符。最后将当前算符压入栈中。当所有的输入都被处理完后，从栈中依次弹出元素并输出。
- 优先级解析器法：优先级解析器法是一种基于递归下降解析器技术的算法，它利用优先级和结合性的规则来生成一个语法分析树，然后遍历这棵语法分析树进行求值。具体来说，该算法将四则运算表达式转换为语法分析树，然后按照遍历树的顺序依次计算节点的值。
- 前缀表达式：前缀表达式也被称为波兰式。将四则运算表达式写成前缀表达式的形式，可以通过栈来求解。在前缀表达式中，操作符出现在操作数之前，因此容易进行计算。具体来说，该算法将四则运算表达式转换为前缀表达式，然后使用栈求解前缀表达式。从右往左扫描表达式，遇到数字直接压入栈中，遇到操作符弹出栈顶两个元素进行计算，将结果重新压入栈中。重复此过程，直到整个表达式求解完成。
2
四则运算代码赏析（栈处理法）
代码语言：javascript复制// 显示计算器主界面
PosX = 200
PosY = 200
InputBox(Caption, "请输入计算表达式：", "1 2*3", PosX, PosY)
// 处理用户输入
input_str = GetInput()
input_len = Len(input_str)
num_stack = List() // 数字栈
op_stack = List() // 操作符栈
for i = 0 To input_len - 1
c = Mid(input_str, i 1, 1)
If c >= "0" And c <= "9" Then
// 如果是数字字符，则将之前的数字字符合并成一个数字
num_str = ""
j = i
While j < input_len And Mid(input_str, j 1, 1) >= "0" And Mid(input_str, j 1, 1) <= "9"
num_str = num_str Mid(input_str, j 1, 1)
j = j 1
Wend
num = Val(num_str)
num_stack.Add(num)
i = j - 1
ElseIf c = "(" Then
// 如果是左括号，则将其压入操作符栈
op_stack.Add(c)
ElseIf c = ")" Then
// 如果是右括号，则弹出操作符栈中的操作符进行计算，直到遇到左括号
While op_stack.Count > 0 And op_stack[op_stack.Count - 1] <> "("
num2 = num_stack[num_stack.Count - 1]
num_stack.Remove(num2)
num1 = num_stack[num_stack.Count - 1]
num_stack.Remove(num1)
op = op_stack[op_stack.Count - 1]
op_stack.Remove(op)
If op = " " Then
result = num1 num2
ElseIf op = "-" Then
result = num1 - num2
ElseIf op = "*" Then
result = num1 * num2
ElseIf op = "/" Then
result = num1 / num2
End If
num_stack.Add(result)
Wend
op_stack.Remove("(")
ElseIf c = " " Or c = "-" Or c = "*" Or c = "/" Then
// 如果是操作符，则弹出操作符栈中的高优先级操作符进行计算
While op_stack.Count > 0 And op_stack[op_stack.Count - 1] <> "(" And GetPrecedence(op_stack[op_stack.Count - 1]) >= GetPrecedence(c)
num2 = num_stack[num_stack.Count - 1]
num_stack.Remove(num2)
num1 = num_stack[num_stack.Count - 1]
num_stack.Remove(num1)
op = op_stack[op_stack.Count - 1]
op_stack.Remove(op)
If op = " " Then
result = num1 num2
ElseIf op = "-" Then
result = num1 - num2
ElseIf op = "*" Then
result = num1 * num2
ElseIf op = "/" Then
result = num1 / num2
End If
num_stack.Add(result)
Wend
op_stack.Add(c)
End If
Next
// 处理操作符栈中剩余的操作符
While op_stack.Count > 0
num2 = num_stack[num_stack.Count - 1]
num_stack.Remove(num2)
num1 = num_stack[num_stack.Count - 1]
num_stack.Remove(num1)
op = op_stack[op_stack.Count - 1]
op_stack.Remove(op)
If op = " " Then
result = num1 num2
ElseIf op = "-" Then
result = num1 - num2
ElseIf op = "*" Then
result = num1 * num2
ElseIf op = "/" Then
result = num1 / num2
End If
num_stack.Add(result)
Wend
// 显示计算结果
PosX = 200
PosY = 300
OutputBox(Caption, "计算结果为：" Str(num_stack[0]), PosX, PosY)
// 定义一个函数用于获取操作符的优先级
Function GetPrecedence(op)
If op = " " Or op = "-" Then
Return 1
ElseIf op = "*" Or op = "/" Then
Return 2
Else
Return 0
End If
End Function
这个程序使用两个栈（数字栈和操作符栈）来完成表达式求值，并且支持括号优先级。在代码中，我们首先调用 InputBox 函数获取用户输入的表达式，然后依次处理字符串中的每个字符，根据不同的字符类型进行不同的操作。
当我们遇到数字时，需要将数字合并成一个完整的数值，然后将其压入数字栈中。当我们遇到左括号时，需要将其压入操作符栈中。当我们遇到右括号时，需要弹出操作符栈中的操作符进行计算，直到遇到左括号为止。当我们遇到操作符时，需要弹出操作符栈中的高优先级操作符进行计算，然后将当前操作符压入操作符栈中。最后，我们需要处理操作符栈中剩余的操作符，直到操作符栈为空。
在代码中，我们还定义了一个名为 GetPrecedence 的函数，它用于获取操作符的优先级。这个函数返回一个整数值，表示操作符的优先级。
-END-
© Copyright
奔跑的键盘侠原创作品 | 尽情分享朋友圈 | 转载请联系授权
