这是奔跑的键盘侠的第200篇文章
作者|我是奔跑的键盘侠
来源|奔跑的键盘侠(ID:runningkeyboardhero)
转载请联系授权
编写一个函数,要求能够实现字符串表达式的四则运算,并支持括号优先级的特性,要求:必须使用自己的算法实现表达式拆解。
这道题目算是编程领域老生常谈的题目,而且也是计算器实现的基本算法。但是对应业余选手来讲,还是要费点脑力值的。话说当年六级认证时,有遭遇这道题目,绞尽脑汁,那会网上没有什么代码参考,有的倒是各种算法说明,看得眼花缭乱,特别是这个括号相关的种种……
1
四则运算中括号的常见处理算法
2
四则运算代码赏析(栈处理法)
// 显示计算器主界面
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
奔跑的键盘侠原创作品 | 尽情分享朋友圈 | 转载请联系授权