中缀表达式求值算法：栈结构实现

中缀表达式求值算法 中缀表达式求值是计算机科学中的一种重要算法，用于计算中缀表达式的值。中缀表达式是一种将运算符号和操作数混杂在一起的表达式，例如 2*3 或者 10/5。为了计算这些表达式的值，需要使用栈结构来存储运算符号和操作数，并通过优先级关系来确定计算顺序。 算法框架： floatevaluate(char*S,char*&RPN){ stack<float>opnd; stack<char>optr; optr.push('\0'); while(!optr.empty()){ if(isdigit(*S)){ readNumer(S,opnd); } else{ switch(orderBetween(optr.top(),*S)){ /*分别处理*/ } } } return opnd.top(); } 在这个算法框架中，我们使用两个栈：opnd 栈用于存储操作数，optr 栈用于存储运算符号。我们从左到右扫描中缀表达式，每遇到一个运算符号或操作数，就将其压入相应的栈中。然后，我们使用优先级关系来确定运算符号的计算顺序。 优先级关系： 在计算中缀表达式时，需要确定运算符号的优先级关系。我们可以使用以下表格来确定优先级关系： | | + | - | * | / | ( | ) | | --- | --- | --- | --- | --- | --- | --- | | + | > | < | > | > | > | > | | - | < | > | > | > | > | > | | * | < | < | > | > | > | > | | / | < | < | > | > | > | > | | ( | < | < | < | < | > | > | | ) | > | > | > | > | > | > | 在这个表格中，我们可以看到不同的运算符号之间的优先级关系。例如，+ 号的优先级低于 * 号，所以当我们扫描到一个 + 号时，如果栈顶部的运算符号是 * 号，那么我们需要将 * 号计算完毕后，再计算 + 号。 实现算法： 在实现算法时，我们可以使用以下步骤： 1. 初始化两个栈：opnd 栈和 optr 栈。 2. 扫描中缀表达式，从左到右扫描每个运算符号或操作数。 3. 如果遇到一个操作数，就将其压入 opnd 栈中。 4. 如果遇到一个运算符号，就将其压入 optr 栈中，并根据优先级关系来确定计算顺序。 5. 使用 switch 语句来处理不同的运算符号。 6. 计算完毕后，返回 opnd 栈中的最后一个元素作为结果。 中缀表达式求值算法是一种重要的算法，用于计算中缀表达式的值。通过使用栈结构和优先级关系，我们可以正确地计算中缀表达式的值。