pta 7-1 表达式求值数据结构

### PTA 7-1 表达式求值数据结构实现方法及解析 #### 使用栈来处理算术表达式求值 为了有效地解决算术表达式的求值问题，可以采用两个栈的方法：一个用于存储操作数（数值），另一个用于存储运算符。这种方法不仅适用于基本的四则运算，还支持带有括号的复杂表达式。 对于给定的一个中缀表达式，可以通过以下方式将其转换为后缀表达式并完成求值： 1. 初始化两个栈：`operandStack` 和 `operatorStack`。 2. 遍历输入字符串中的每一个字符： - 如果遇到的是数字，则继续读取直到完整的数字被识别出来，并压入到 `operandStack` 中[^1]。 - 若当前字符是一个左括号 '(' ，直接推入 `operatorStack`。 - 当碰到右括号 ')' 时，持续弹出 `operatorStack` 的顶部元素并对相应的操作数执行对应的二元运算，直至遇见匹配的左括号为止，此时应丢弃这对括号。 - 对于其他任何运算符 (+, -, *, /)，遵循一定的优先级规则决定何时将新来的运算符放入 `operatorStack` 或者立即应用已有的最高优先级的操作。 3. 完成遍历之后，如果还有剩余未处理的运算符存在于 `operatorStack` 内部，则依次取出这些运算符并与剩下的操作数一起参与计算，最后留在 `operandStack` 上面的那个唯一元素即为我们想要的结果。 下面给出一段 Python 代码作为例子展示如何具体实施这一算法逻辑: ```python def evaluate_expression(expression): precedence = {'+':1, '-':1, '*':2, '/':2} def apply_operation(operators, values): operator = operators.pop() right = values.pop() left = values.pop() if operator == '+': values.append(left + right) elif operator == '-': values.append(left - right) elif operator == '*': values.append(left * right) elif operator == '/': values.append(int(left / float(right))) def greater_precedence(op1, op2): return precedence[op1] >= precedence[op2] operators = [] operands = [] i = 0 while i < len(expression): if expression[i].isdigit(): val = 0 while (i < len(expression) and expression[i].isdigit()): val = (val * 10) + int(expression[i]) i += 1 operands.append(val) continue elif expression[i] == '(': operators.append(expression[i]) elif expression[i] == ')': while operators[-1] != '(': apply_operation(operators, operands) operators.pop() else: while ((operators) and operators[-1]!='(' and greater_precedence(operators[-1],expression[i])): apply_operation(operators,operands) operators.append(expression[i]) i+=1 while operators: apply_operation(operators, operands) return operands[0] ``` 此函数接收一个由数字和运算符组成的字符串形式的数学表达式，并返回其评估后的整数值。注意这里假设所有的除法都是精确无余数的情况下的整数除法。