按键精灵进阶之路——考级题目002

Ed_Frey

发布于 2023-08-28 15:04:55

1400

发布于 2023-08-28 15:04:55

文章被收录于专栏：奔跑的键盘侠奔跑的键盘侠

这是奔跑的键盘侠的第200篇文章

作者|我是奔跑的键盘侠

来源|奔跑的键盘侠（ID：runningkeyboardhero）

转载请联系授权

编写一个函数，要求能够实现字符串表达式的四则运算，并支持括号优先级的特性，要求：必须使用自己的算法实现表达式拆解。

这道题目算是编程领域老生常谈的题目，而且也是计算器实现的基本算法。但是对应业余选手来讲，还是要费点脑力值的。话说当年六级认证时，有遭遇这道题目，绞尽脑汁，那会网上没有什么代码参考，有的倒是各种算法说明，看得眼花缭乱，特别是这个括号相关的种种……

四则运算中括号的常见处理算法

递归求解法：递归求解法是最普遍、最自然的方法之一。它的思路是逐层拆分表达式并递归求解。具体来说，对于一个包含括号的表达式，首先将最内层的括号表达式拆分出来，然后递归地求解这个括号表达式。将求解结果带回原表达式中，继续拆分和求解直到所有的括号被去除。
栈处理法：栈处理法是另一种常见的方法。它的基本思路是用两个栈（一个操作数栈和一个操作符栈）来实现计算。遇到数字时将其压入操作数栈，遇到算符时将其压入操作符栈。当遇到右括号时，从操作数栈中弹出两个数，从操作符栈中弹出对应的算符进行运算，将结果压入操作数栈中。重复此过程，直到左括号被弹出为止。
中缀表达式转后缀表达式：中缀表达式转后缀表达式也是一种常用的处理方法。具体来说，该算法将中缀表达式转换为后缀表达式，再使用后缀表达式求解。转换过程中需要借助一个栈来实现。遇到数字时直接输出，遇到算符时将其压入栈中。如果栈顶元素是同级或更高优先级的算符，则弹出栈顶元素并输出，重复此过程直到栈为空或者栈顶元素优先级低于当前算符。最后将当前算符压入栈中。当所有的输入都被处理完后，从栈中依次弹出元素并输出。
优先级解析器法：优先级解析器法是一种基于递归下降解析器技术的算法，它利用优先级和结合性的规则来生成一个语法分析树，然后遍历这棵语法分析树进行求值。具体来说，该算法将四则运算表达式转换为语法分析树，然后按照遍历树的顺序依次计算节点的值。
前缀表达式：前缀表达式也被称为波兰式。将四则运算表达式写成前缀表达式的形式，可以通过栈来求解。在前缀表达式中，操作符出现在操作数之前，因此容易进行计算。具体来说，该算法将四则运算表达式转换为前缀表达式，然后使用栈求解前缀表达式。从右往左扫描表达式，遇到数字直接压入栈中，遇到操作符弹出栈顶两个元素进行计算，将结果重新压入栈中。重复此过程，直到整个表达式求解完成。

四则运算代码赏析（栈处理法）

// 显示计算器主界面
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-

奔跑的键盘侠原创作品 | 尽情分享朋友圈 | 转载请联系授权

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2023-06-10，如有侵权请联系 cloudcommunity@tencent.com 删除

stack