数据结构 基于栈的算术表达式求值

### 使用栈数据结构实现算术表达式求值

为了直接处理中缀算术表达式而不将其转换为其他形式，可以采用双栈法。此方法涉及两个栈：一个是用于存储操作数的操作数栈(OPND)，另一个是用于存储运算符的运算符栈(OPTR)[^1]。

#### 初始化阶段
- 将`OPND`栈初始化为空。
- `OPTR`栈被初始化并放置一个特殊符号'#'表示表达式的起始标志[^2]。

#### 处理流程
当逐个字符解析给定的中缀表达式时：

对于遇到的操作数（即数字），应立即将其转化为浮点型数值并推入到`OPND`栈内。

面对非操作数情况，也就是遇到了运算符的时候，则需遵循如下逻辑：
- 对比新读取到的运算符与位于`OPTR`栈顶端的那个之间的优先级别；
- 如果新的运算符拥有更高的优先级，则它会被压入`OPTR`栈等待后续处理；
- 反之如果现有的栈顶运算符具有较高或相等的优先度，那么就应当先执行该次运算——具体做法是从`OPND`栈取出最近两次存入的操作数，并依据从`OPTR`弹出的运算符完成一次计算，之后把得到的结果重新送回至`OPND`栈顶部位置；
- 特殊情况下，若两者均为相同类型的括号（比如一对匹配的小括弧()），这表明子表达式的结束，此时仅需简单移除对应开闭括号而无需做任何实际运算。

最终，在整个字符串遍历完毕后，剩余在`OPND`栈上的唯一元素便是所求得的答案。

下面给出一段Python代码示例来展示这一过程:

def evaluate_expression(expression):
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2}
    
    opnd_stack = []      # 操作数栈
    opt_stack = ['#']     # 运算符栈
    
    i = 0
    while i < len(expression) or opt_stack[-1] != '#':
        char = expression[i]

        if '0' <= char <= '9' or char == '.':
            num_str = ''
            while i < len(expression) and ('0' <= expression[i] <= '9' or expression[i] == '.'):
                num_str += expression[i]
                i += 1
            
            opnd_stack.append(float(num_str))
            continue
        
        elif char in '+-1]]:
                opt_stack.append(char)
            else:
                while precedence[char] <= precedence[opt_stack[-1]] and opt_stack[-1]!='#':
                    operator = opt_stack.pop()
                    operand2 = opnd_stack.pop()
                    operand1 = opnd_stack.pop()

                    result = apply_operator(operator, operand1, operand2)
                    opnd_stack.append(result)

                opt_stack.append(char)
        
        elif char == ')':
            top_opt = opt_stack.pop()
            while top_opt != '(':
                operand2 = opnd_stack.pop()
                operand1 = opnd_stack.pop()

                result = apply_operator(top_opt, operand1, operand2)
                opnd_stack.append(result)

                top_opt = opt_stack.pop()
                
        i+=1
                
    return opnd_stack[0]


def apply_operator(op, a, b):
    operations = {
        "+": lambda x,y : x+y,
        "-": lambda x,y : x-y,
        "*": lambda x,y : x*y,
        "/": lambda x,y : x/y
    }
    return operations[op](a,b)


if __name__ == "__main__":
    expr = "3 + (5 * 7 - 8 / 4)"
    print(f"The value of '{expr}' is {evaluate_expression(expr)}")