基于栈的算术表达式求值

### 使用栈实现算术表达式求值 为了计算算术表达式的值，可以采用双栈法：一个是用于存储操作数的栈 `OPND`，另一个是用于存储操作符的栈 `OPTR`。通过这种方式能够有效地处理带有括号以及不同优先级运算符的情况。 #### 初始化阶段 - 将操作数栈 `OPND` 置为空； - 向操作符栈 `OPTR` 压入一个特殊符号 `#` 表示初始状态下的最低优先级[^4]。 #### 处理过程 当自左至右扫描输入字符串时： - 如果遇到的是数字，则继续读取直到获取完整的数值并将其转换成整型后推入 `OPND` 栈中。 - 若当前字符为运算符（包括括号），则需按照一定规则与 `OPTR` 的栈顶元素比较其优先级别： - 当前新读入的操作符比栈顶高时，直接将该操作符压入 `OPRT` 栈。 - 新旧两者的优先度相等但不是终止标志 `#` 时，意味着遇到了匹配的一对括号，这时应该弹出 `OPTR` 栈内的对应开闭括号。 - 反之，若新的操作符低于或等于栈顶者，则从 `OPND` 出栈两个最近加入的数据作为被操作对象，并取出 `OPTR` 上面的一个操作符执行相应的数学运算，之后把得到的结果再次放入 `OPND` 中等待后续可能存在的其他运算。 此循环持续到整个表达式遍历完毕为止，最后留在 `OPND` 中的就是所求得的答案。 下面给出一段 Python 实现上述逻辑的例子: ```python def eval_expr(expression): precedence = {'+':1, '-':1, '*':2, '/':2} opnd = [] # operand stack (for numbers) optor = ['#'] # operator stack i = 0 while i < len(expression) or optor[-1]!='#' : if '0'<=expression[i]<='9': num = '' while i<len(expression) and ('0'<=expression[i]<='9'): num += expression[i] i+=1 opnd.append(int(num)) continue elif expression[i]=='(': optor.append('(') elif expression[i]==')': while optor[-1]!='(': calc(opnd,optor) optor.pop() # remove '(' from the top of OPTOR else: # encounter an arithmetic operator cur_optr = expression[i] while(precedence.get(optor[-1],0)>=precedence[cur_optr]): calc(opnd,optor) optor.append(cur_optr) i+=1 return opnd[-1] def calc(opnds,optors): b,a = opnds.pop(),opnds.pop() oper = optors.pop() res = { '+': lambda a,b :a+b, '-': lambda a,b:a-b, '*': lambda a,b:a*b, '/': lambda a,b:int(a/b), }[oper](a,b) opnds.append(res) if __name__ == "__main__": expr = "(7+15)*(23-28/4)" result = eval_expr(expr.replace(" ","")) print(f"The value of {expr} is {result}.") ```