算法5.12-5.13表达式求值

算法5.12-5.13通常是指用于表达式求值的算法。这类算法在编译原理和编程语言解释器中非常重要。以下是对这类算法的介绍：

1. 中缀表达式转后缀表达式（算法5.12）：
这个过程通常使用栈来实现。算法的基本步骤如下：
- 创建一个空栈用于存储运算符
- 创建一个空列表用于存储输出
- 遍历中缀表达式的每个符号：
* 如果是操作数，直接添加到输出列表
* 如果是左括号，压入栈中
* 如果是右括号，弹出栈中元素并添加到输出，直到遇到左括号
* 如果是运算符，当栈顶运算符的优先级大于或等于当前运算符时，弹出栈顶运算符并添加到输出，然后将当前运算符压入栈中
- 遍历结束后，将栈中剩余的运算符全部弹出并添加到输出

2. 后缀表达式求值（算法5.13）：
这个过程也使用栈来实现。算法的基本步骤如下：
- 创建一个空栈用于存储操作数
- 遍历后缀表达式的每个符号：
* 如果是操作数，将其转换为数值并压入栈中
* 如果是运算符，从栈中弹出两个操作数，应用运算符后将结果压回栈中
- 遍历结束后，栈中剩下的元素就是表达式的最终结果

这些算法的主要优点包括：
- 简单高效：使用栈结构可以有效地处理运算符的优先级
- 易于实现：算法步骤清晰，易于用各种编程语言实现
- 通用性强：可以处理任意复杂的算术表达式

相关问题

头歌算法5.12-5.13表达式求值

### 关于头歌平台中5.12至5.13期间算法表达式求值的内容

在头歌平台上，针对5.12到5.13阶段涉及的表达式求值相关内容主要集中在如何解析并计算算术表达式的值。这部分通常会涉及到栈这一重要数据结构的应用。

#### 使用栈实现表达式求值

为了处理带括号的四则运算表达式，可以采用两个栈来分别存储操作数和操作符。具体过程如下：

- 初始化两个栈：`operandStack`用于保存数值；`operatorStack`用来暂存遇到的操作符。
- 遍历给定字符串形式的表达式中的每一个字符：
- 如果当前字符是一个数字，则继续读取直到整个数字被识别出来，并将其压入`operandStack`[^1]。

while (isdigit(expression[i])) {
    num = num * 10 + expression[i] - '0';
    ++i;
}
operandStack.push(num);

- 当碰到加减乘除符号或其他优先级较低的操作符时，比较其与`operatorStack`顶部元素的优先级关系决定是否执行相应的运算逻辑并将结果重新放入`operandStack`中，之后再把新的操作符加入`operatorStack`。

if (!operatorStack.empty()) {
    while (!operatorStack.empty() && precedence(operatorStack.top(), currentOperator)) {
        performOperation(operandStack, operatorStack);
    }
}
operatorStack.push(currentOperator);

- 对于左括号直接推入`operatorStack`; 右括号意味着要不断弹出`operatorStack`里的操作符直至匹配上对应的左括号为止，在此过程中同样需要更新`operandStack`内的中间结果。

else if (expression[i] == ')') {
    while (!operatorStack.empty() && operatorStack.top() != '(') {
        performOperation(operandStack, operatorStack);
    }
    // Remove the left parenthesis from stack.
    operatorStack.pop();
}

最终当所有字符都被处理完毕后，可能还存在一些未解决的操作留在`operatorStack`里，这时应持续调用`performOperation()`函数直到该栈为空，此时`operandStack`顶端即为所求表达式的解。

复习教材算法5.12和5.13的相关内容，完成表达式树的创建，表达式树的求值。要求编写完整程序，输入算术表达式，并以#结束,中间计算过程要是个位数（例如“3+1*3-6/3”），求解表达式的值。

以下是表达式树的创建和求值的完整程序，使用了算法5.12和5.13的相关内容：

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

class ExpressionTree:
    def __init__(self, expression):
        self.root = None
        self.expression = self.convert_expression(expression)
        
    def convert_expression(self, expression):
        postfix = []
        stack = []
        i = 0
        while i < len(expression):
            if expression[i].isdigit():
                num = 0
                while i < len(expression) and expression[i].isdigit():
                    num = num * 10 + int(expression[i])
                    i += 1
                postfix.append(num)
            elif expression[i] in "+-*/":
                while stack and self.precedence(stack[-1]) >= self.precedence(expression[i]):
                    postfix.append(stack.pop())
                stack.append(expression[i])
                i += 1
            elif expression[i] == "(":
                stack.append(expression[i])
                i += 1
            elif expression[i] == ")":
                while stack and stack[-1] != "(":
                    postfix.append(stack.pop())
                stack.pop()
                i += 1
        while stack:
            postfix.append(stack.pop())
        return postfix
    
    def precedence(self, operator):
        if operator in "+-":
            return 1
        elif operator in "*/":
            return 2
        else:
            return 0
    
    def build_tree(self):
        stack = []
        for token in self.expression:
            if isinstance(token, int):
                node = TreeNode(token)
                stack.append(node)
            else:
                node = TreeNode(token)
                node.right = stack.pop()
                node.left = stack.pop()
                stack.append(node)
        self.root = stack.pop()
    
    def evaluate_tree(self):
        return self.evaluate_node(self.root)
    
    def evaluate_node(self, node):
        if isinstance(node.val, int):
            return node.val
        left_val = self.evaluate_node(node.left)
        right_val = self.evaluate_node(node.right)
        if node.val == "+":
            return left_val + right_val
        elif node.val == "-":
            return left_val - right_val
        elif node.val == "*":
            return left_val * right_val
        elif node.val == "/":
            return left_val / right_val

expression = input("请输入算术表达式，以#结束:")
tree = ExpressionTree(expression)
tree.build_tree()
result = tree.evaluate_tree()
print("表达式的值为: %.0f" % result)

使用方法：

请输入算术表达式，以#结束:3+1*3-6/3#
表达式的值为: 6