《大话数据结构》第4章实战：中缀表达式转后缀 + 后缀表达式求值（完整可运行实现）

1. 引言四则运算表达式是我们从小学就开始接触的数学工具比如3(4*5-2)/2。对人来说一眼就能看出先算括号里的4*5再算20-2然后除以2最后加上3。但计算机面对同样的表达式却一头雾水——它不知道运算符的优先级也不理解括号的嵌套关系。《大话数据结构》第 4.9 节用栈这一数据结构优雅地解决了四则运算问题。核心思路分两步先把中缀表达式转成后缀表达式逆波兰表示法再对后缀表达式求值。这篇博客给出完整、可处理多位数和括号的 C 实现并对算法细节做了深入剖析。2. 核心概念三种表达式在正式写代码之前先理清三种表达式的区别表达式类型示例特点中缀表达式3 4 * 5运算符在两个操作数中间符合人类习惯但有优先级和括号问题前缀表达式波兰式 3 * 4 5运算符在操作数前面无需括号即可表达优先级后缀表达式逆波兰式3 4 5 * 运算符在操作数后面计算机求值最方便无需括号后缀表达式之所以适合计算机处理是因为它天然消除了优先级和括号遇到数字就压栈遇到运算符就弹出两个操作数计算结果再压回去。整个过程不需要前瞻或回溯。我们要做的就是把中缀表达式转换成这种结构。3. 中缀转后缀算法详解3.1 算法核心思想中缀转后缀的核心是用栈管理运算符。遍历中缀表达式的每个字符按以下规则处理遇到数字直接输出到后缀表达式注意处理多位数。遇到左括号(直接压入运算符栈。遇到右括号)不断弹出栈顶运算符并输出直到遇到左括号为止最后把左括号弹出丢弃。遇到运算符和栈顶运算符比较优先级。如果栈顶运算符优先级大于等于当前运算符就弹出栈顶并输出直到栈为空或栈顶优先级更低然后把当前运算符压栈。遍历结束后把栈中剩余的运算符全部弹出输出。下面用一个实例走一遍中缀表达式3(4*5-2)/2的转换过程。步骤当前字符运算符栈后缀输出说明13空3数字直接输出23栈空直接压栈3( (3左括号直接压栈44 (3 4数字直接输出5* ( *3 4栈顶是(*直接压栈65 ( *3 4 5数字直接输出7- ( -3 4 5 *-优先级低于*弹出*后压入-82 ( -3 4 5 * 2数字直接输出9)3 4 5 * 2 -弹出-再弹出(丢弃10/ /3 4 5 * 2 -/优先级高于直接压栈112 /3 4 5 * 2 - 2数字直接输出12结束空3 4 5 * 2 - 2 / 弹出剩余运算符/和最终后缀表达式为3 4 5 * 2 - 2 / 这正是我们期望的结果。3.2 优先级函数优先级判断是整个算法的基石。乘除的优先级高于加减括号本身不参与优先级比较int priority(char op) { if (op || op -) return 1; if (op * || op /) return 2; return 0; // 括号返回 0保证不会错误弹出 }这里把(的优先级设为 0 是关键设计当栈顶是左括号时任何运算符都不会因为优先级比较而被错误弹出因为左括号的优先级最低。3.3 完整转换代码string infixToPostfix(const string infix) { stackchar opStack; string postfix; for (size_t i 0; i infix.size(); i) { char c infix[i]; if (isdigit(c)) { // 处理多位数连续读取直到非数字 while (i infix.size() isdigit(infix[i])) { postfix infix[i]; } postfix ; // 用空格分隔操作数 --i; // 回退外层 for 会 i } else if (c () { opStack.push(c); } else if (c )) { // 弹出直到遇到左括号 while (!opStack.empty() opStack.top() ! () { postfix opStack.top(); postfix ; opStack.pop(); } opStack.pop(); // 弹出 ( 并丢弃 } else if (c || c - || c * || c /) { // 栈顶优先级大于等于当前运算符时弹出 while (!opStack.empty() priority(opStack.top()) priority(c)) { postfix opStack.top(); postfix ; opStack.pop(); } opStack.push(c); } } // 弹出栈中剩余运算符 while (!opStack.empty()) { postfix opStack.top(); postfix ; opStack.pop(); } return postfix; }这段代码有两个容易忽略的细节多位数处理内层while循环连续读取数字字符保证像12、345这样的多位数被完整输出为一个操作数。空格分隔每个操作数和运算符后面都追加一个空格这是为了让后缀表达式求值阶段能够用stringstream按空格切分 token。4. 后缀表达式求值4.1 算法思想拿到后缀表达式后求值反而简单了——只需要一个操作数栈。遍历后缀表达式中的每个 token如果是数字压入操作数栈。如果是运算符从栈中弹出两个操作数先弹出的是右操作数b后弹出的是左操作数a计算a op b把结果压回栈中。遍历结束后栈中剩下的唯一元素就是最终结果。以3 4 5 * 2 - 2 / 为例步骤当前 token操作数栈操作13[3]数字入栈24[3, 4]数字入栈35[3, 4, 5]数字入栈4*[3, 20]弹出 5 和 4计算 4*520压回52[3, 20, 2]数字入栈6-[3, 18]弹出 2 和 20计算 20-218压回72[3, 18, 2]数字入栈8/[3, 9]弹出 2 和 18计算 18/29压回9[12]弹出 9 和 3计算 3912压回最终栈中只剩12与预期一致。4.2 完整求值代码double evaluatePostfix(const string postfix) { stackdouble numStack; stringstream ss(postfix); string token; while (ss token) { // 判断是否为数字支持负数如 -3 if (isdigit(token[0]) || (token.size() 1 token[0] -)) { numStack.push(stod(token)); } else { double b numStack.top(); numStack.pop(); double a numStack.top(); numStack.pop(); switch (token[0]) { case : numStack.push(a b); break; case -: numStack.push(a - b); break; case *: numStack.push(a * b); break; case /: numStack.push(a / b); break; } } } return numStack.top(); }注意这里用stod(token)将字符串转为double这样即使表达式中有小数也能正确处理。另外数字判断中加了token.size() 1 token[0] -是为了识别像-3这样的负数 token。5. 完整可运行代码把上述两部分拼在一起加上必要的头文件和测试用例得到一份完整的可运行程序#include iostream #include stack #include string #include sstream #include cctype using namespace std; int priority(char op) { if (op || op -) return 1; if (op * || op /) return 2; return 0; } string infixToPostfix(const string infix) { stackchar opStack; string postfix; for (size_t i 0; i infix.size(); i) { char c infix[i]; if (isdigit(c)) { while (i infix.size() isdigit(infix[i])) { postfix infix[i]; } postfix ; --i; } else if (c () { opStack.push(c); } else if (c )) { while (!opStack.empty() opStack.top() ! () { postfix opStack.top(); postfix ; opStack.pop(); } opStack.pop(); } else if (c || c - || c * || c /) { while (!opStack.empty() priority(opStack.top()) priority(c)) { postfix opStack.top(); postfix ; opStack.pop(); } opStack.push(c); } } while (!opStack.empty()) { postfix opStack.top(); postfix ; opStack.pop(); } return postfix; } double evaluatePostfix(const string postfix) { stackdouble numStack; stringstream ss(postfix); string token; while (ss token) { if (isdigit(token[0]) || (token.size() 1 token[0] -)) { numStack.push(stod(token)); } else { double b numStack.top(); numStack.pop(); double a numStack.top(); numStack.pop(); switch (token[0]) { case : numStack.push(a b); break; case -: numStack.push(a - b); break; case *: numStack.push(a * b); break; case /: numStack.push(a / b); break; } } } return numStack.top(); } int main() { // 测试用例 1 string infix1 3(4*5-2)/2; string postfix1 infixToPostfix(infix1); cout 中缀: infix1 endl; cout 后缀: postfix1 endl; cout 结果: evaluatePostfix(postfix1) endl; // 12 cout --- endl; // 测试用例 2多位数 string infix2 1234*5; string postfix2 infixToPostfix(infix2); cout 中缀: infix2 endl; cout 后缀: postfix2 endl; cout 结果: evaluatePostfix(postfix2) endl; // 182 cout --- endl; // 测试用例 3嵌套括号 string infix3 ((23)*4-(5-2))/3; string postfix3 infixToPostfix(infix3); cout 中缀: infix3 endl; cout 后缀: postfix3 endl; cout 结果: evaluatePostfix(postfix3) endl; // 5.66667 return 0; }6. 运行结果与分析编译运行上述代码输出如下中缀: 3(4*5-2)/2 后缀: 3 4 5 * 2 - 2 / 结果: 12 --- 中缀: 1234*5 后缀: 12 34 5 * 结果: 182 --- 中缀: ((23)*4-(5-2))/3 后缀: 2 3 4 * 5 2 - - 3 / 结果: 5.66667三个测试用例覆盖了基础四则运算与括号嵌套、多位数处理、多层嵌套括号三种典型场景全部输出正确结果。7. 拓展思考这套代码已经能正确处理多位数、括号和四则运算优先级。如果想让实现更健壮以下几个方向值得进一步探索支持小数当前代码只处理整数数字可以在isdigit判断中加入对小数点.的处理。支持负数中缀表达式中的一元负号如-35或3*(-2)需要特殊处理因为同一个-符号可能是二元减法也可能是一元取负。支持更多运算符比如幂运算^右结合或取模%需要调整优先级函数和结合性规则。错误处理对非法输入如不匹配的括号、连续运算符等给出友好提示。用模板/泛型改写让求值函数支持int、long long、double等多种数值类型。8. 总结中缀转后缀加后缀求值是栈的经典应用场景也是《大话数据结构》第 4 章的高光内容。整个方案的核心就两句话转后缀靠运算符栈——用优先级比较决定运算符的输出时机括号用来界定子表达式的边界。求值靠操作数栈——见到数字就压见到运算符就弹两个算一个再压回去。理解了这个双栈协作的模式再去理解编译原理中的表达式解析、甚至是逆波兰计算器的实现都会轻松很多。建议读者把代码复制到本地跑一遍然后试着改几个表达式观察后缀输出手感会更好。