双栈实现基于上文对后缀表达式的操作与解释。现在正式展示具体的代码实现。首先最重要的我们需要两个和栈数值栈和运算符栈。在遍历时需要同时对后缀表达式的生成方式和计算方式这两方面同步进行。核心就是在每次运算符栈的弹栈操作均伴随着一次数值的计算共三处遍历到运算符遍历到右括号遍历完处理非空的运算符栈根据运算符的种类对数值栈的栈顶元素和栈顶倒数第二个元素进行运算并将计算结果再次保存到数值栈中。预处理和辅助细节过滤原表达式无用的空格。对于单元运算符 /- 在左括号后的出现可以添加占位 0 构成 0 num 或 0 - num 的操作。对于一些特殊表达式如 -1 可以在数字栈放一个占位的 0保证每次的操作在数字栈中能有至少两个操作数。可以用一个哈希表维护各类运算符的优先级问题。下面是实例分析基本计算器 III 包含加减乘除小括号的综合应用展示。class Solution { private: // 规定运算符优先级 unordered_mapchar, int level { {, 1}, {-, 1}, {*, 2}, {/, 2}, }; // 预处理 // 过滤1. 空格 // 过滤2. 增加前导0 string filter(string t) { string s; // 过滤空格 stringstream ss(t); while (ss t) { s t; } // (- (0- for (int pos s.find((-); pos ! string::npos; pos s.find((-, pos)) { s.insert(pos 1, 0); } // ( (0 for (int pos s.find((); pos ! string::npos; pos s.find((, pos)) { s.insert(pos 1, 0); } return s; } // 单次操作 void calcStack(stackint numStk, stackchar opStk) { const int num numStk.top(); numStk.pop(); const char op opStk.top(); opStk.pop(); if (op ) { numStk.top() num; } else if (op -) { numStk.top() - num; } else if (op *) { numStk.top() * num; } else if (op /) { numStk.top() / num; } } public: int calculate(string s) { // 预处理字符串 s filter(s); // 数字栈运算符栈 stackint numStk; stackchar opStk; // 添加哨兵数字0 numStk.push(0); for (int i 0; i s.size(); i 1) { if (isdigit(s[i])) { int sum 0; for (; i s.size() isdigit(s[i]); i 1) { sum 10 * sum (s[i] - 0); } i -1; numStk.push(sum); } else { const char curOp s[i]; if (curOp () { opStk.push(curOp); } else if (curOp )) { // 不断弹栈直到出现( while (!opStk.empty() opStk.top() ! () { calcStack(numStk, opStk); } // 处理到最后的( opStk.pop(); } else { // 根据运算符优先级 while (!opStk.empty() opStk.top() ! ( level[opStk.top()] level[curOp]) { calcStack(numStk, opStk); } opStk.push(curOp); } } // if else } // for // 最后处理剩余的运算 while (!opStk.empty()) { calcStack(numStk, opStk); } // 最后栈顶的就是答案 return numStk.top(); } };小结表达式求值是数据结构的学习中非常经典的一个应用。将中缀表达式化为后缀表达式的核心就是两点后缀表达式的单次计算方式后缀表达式的生成方式。在考研中一般要求学生能够写出单次计算和后缀表达式生成的全过程。而求职中则需要能够 ac 掉笔试的代码题。因此每位读者都应该熟练掌握应对知识点和方法。最后基于双栈的方法除了处理本文中提到的常见四则运算外还可以针对四则运算以外的运算符或者自定义的运算符进行处理。对于这点读者可以作为拓展自行尝试。
