Dijkstra发明的调度场算法用于将中缀表达式转为前缀或后缀表达式本文目的是简要介绍调度场算法并给出分析和说明网上众多作者采用自然语言描述转换算法因此对转换算法的描述不够清晰直观。这里花费了一点时间绘制了中缀转后缀前缀的算法流程图用流程图描述转换算法更直观易懂便于读者学习绘制的流程图如下。为简化问题假设要处理的中缀表达式只由算术运算符-*/和圆括号()组合而成。中缀转前缀算法和中缀转后缀完全类似只不过转后缀需要从左至右扫描表达式转前缀正好相反此外后缀算法中左右括号为前缀算法的右左括号优先级判断条件前缀算法为大于等于后缀算法为大于前缀后缀算法再最后输出中间结果栈中的转换结果时输出顺序正好相反后缀为从栈底到栈顶前缀为从栈顶到栈底。流程图中把操作符和操作数统称为词本文中圆括号不是运算符仅用于改变运算顺序为了方便读者学习制作了一张中缀转后缀算法执行过程的示意表格。中缀转前缀执行过程完全类似读者可拿来练手以上算法仅考虑二元运算符若优先级相同则具有左结合性如果同时考虑相同优先级具有右结合性的二元运算符则求后缀表达式的流程图中右下角的方框内应该改为:如果当前操作符优先级小于栈顶操作符优先级则将栈顶操作符弹出操作符栈压入中间结果栈否则如果当前操作符优先级等于栈顶操作符优先级若当前操作符和栈顶操作符具有左结合性则将栈顶操作符弹出操作符栈压入中间结果栈若具有右结合性则将当前操作符压入操作符栈然后操作结束。如果操作始终未结束则不断重复以上操作直到操作符栈空遇到左括号或栈顶操作符优先级小于当前操作符优先级为止然后将当前操作符压入操作符栈然后操作结束。以上论述用到的不变量没有对操作符栈操作的任何时刻从操作符栈底到栈顶的操作符执行优先级依次升高即更靠近栈顶的操作符的执行次序一定先于栈中其下的操作符对于求前缀表达式的算法,注意算法输出前缀表达式应该从栈顶到栈底输出这意味着前缀表达式中执行优先级较高的运算符应当更靠近中间结果栈栈底较低的更靠近栈顶由于算法执行过程中需要从操作符栈中弹出操作符压入中间结果栈因此执行优先级高的运算符应当靠近操作符栈栈顶较低的靠近栈底这意味着求前缀表达式算法所用不变量和求后缀表达式算法所用不变量(见以上红字部分)是一致的(PS:后缀表达式的分析是类似的)。如果求前缀表达式也要考虑相同优先级具有右结合性的运算符则应把前缀表达式算法流程图最右下菱形红框中的大于等于改为大于最右下角蓝色矩形方框中的内容应该改为如果当前操作符优先级小于栈顶操作符优先级则将栈顶操作符弹出操作符栈压入中间结果栈否则如果当前操作符优先级等于栈顶操作符优先级若当前操作符和栈顶操作符具有右结合性则将栈顶操作符弹出操作符栈压入中间结果栈若具有左结合性则将当前操作符压入操作符栈然后操作结束。如果操作始终未结束则不断重复以上操作直到操作符栈空遇到右括号或栈顶操作符优先级小于当前操作符优先级为止然后将当前操作符压入操作符栈然后操作结束。下面对以上论述做一点说明1:为什么只考虑左结合二元运算符情况下后缀表达式算法中流程图最右下红色菱形方框判断操作是大于而在前缀表达式算法中最右下角红色菱形方框中的判断操作是大于等于?因为为了使输出的前缀和后缀表达式能够严格反映优先级和结合性决定的运算符执行次序我们在操作中需要维持上文红字部分的不变量(详见红字下方分析)。后缀表达式算法中如果当前操作符优先级等于栈顶操作符优先级而当前操作符和栈顶操作符具有左结合性注意我们从左至右扫描表达式当前操作符在表达式右边栈顶操作符在左边这意味着栈顶操作符执行优先级高此时若将当前操作符压入操作符栈会破坏不变量所以应当转入NO对应情形处理。而在前缀表达式算法中如果当前操作符优先级等于栈顶操作符优先级而当前操作符和栈顶操作符具有左结合性注意我们从右向左扫描表达式当前操作符在表达式左边栈顶操作符在右边这意味着当前操作符执行优先级高故可压栈而不会破坏不变量2:在考虑相同优先级具有右结合性的二元运算符的情形下对算法流程图所做修改的含义是什么?考虑后缀表达式算法流程图右下角方框如果当前操作符优先级小于栈顶操作符优先级此时直接压入当前操作符会破坏不变量所以我们把栈顶操作符弹出压入中间结果栈(这样能使执行优先级高的靠近中间结果栈栈底)。如果当前操作符优先级等于栈顶操作符优先级若当前操作符和栈顶操作符具有左结合性由上文分析知栈顶操作符优先级高所以要做的和上一情形相同。若当前操作符和栈顶操作符具有右结合性根据扫描顺序(从左往右)当前操作符执行优先级高但是当前操作符的操作数(子表达式)尚未全部进入中间结果栈所以我们直接将当前操作符压入操作符栈这样也不会破坏不变量考虑前缀表达式流程图之所以要把最右下菱形红框中的大于等于改为大于是因为如果当前操作符和栈顶操作符优先级相同且具有右结合性根据扫描顺序(从右至左)栈顶操作符执行优先级高此时将当前操作符压入操作符栈会破坏不变量所以应当改为大于并把等于情形转入NO对应情形(小于等于)处理右下角蓝色矩形方框修改理由和后缀表达式流程图是类似的可自行分析调度场算法的C实现(中缀转后缀和表达式树构建):#include iostream #include string #include map #include vector using namespace std; struct OperatorInfo { int priority; //运算符优先级值越小优先级越高 bool isLeftUnion; //运算符是否为左结合 bool isBinaryOperator; //是否为二元运算符 }; struct ExprTreeNode //表达式树节点 { char operator_or_atomic_operand; //运算符或原子操作数 ExprTreeNode* left nullptr; ExprTreeNode* right nullptr; ExprTreeNode(char o) :operator_or_atomic_operand(o) {} }; bool checkLackOperand(size_t num_of_cur_operand, const OperatorInfo op_info) //检查运算符是否缺少运算分量 { if (op_info.isBinaryOperator) { if (num_of_cur_operand 2) { return false; } else { num_of_cur_operand - 2; num_of_cur_operand; } } else { if (num_of_cur_operand 0) { return false; } } return true; } void check(const char _operator, size_t num_of_cur_operand, const OperatorInfo op_info) { if (checkLackOperand(num_of_cur_operand, op_info) false) { std::cout ERROR:运算符 _operator 缺少运算分量 endl; exit(-1); } } void buildExprTree(vectorExprTreeNode* work_stack, const char _operator, const OperatorInfo op_info) { ExprTreeNode* _new new ExprTreeNode(_operator); if (op_info.isBinaryOperator) { _new-right work_stack.back(); work_stack.pop_back(); } _new-left work_stack.back(); work_stack.pop_back(); work_stack.push_back(_new); } void PostorderTraversal(ExprTreeNode* root) { if (root ! nullptr) { PostorderTraversal(root-left); PostorderTraversal(root-right); std::cout root-operator_or_atomic_operand; } } int main() //本程序假定所有一元运算符是右结合的且具有相同优先级且相同优先级的所有二元运算符具有相同的结合性 { mapchar, OperatorInfo operator_info_list { {~, {1, false, false}}, {!, {1, false, false}}, {, {1, false, false}}, {, {9, false, true}}, {|, {9, false, true}}, {, {8, false, true}}, {, {8, false, true}}, {^, {1, false, false}}, {, {3, true, true}}, {-, {3, true, true}}, {*, {2, true, true}}, {/, {2, true, true}} }; //初始化运算符信息 vectorchar operator_stack; //操作符栈 vectorchar operand_stack; //操作数栈(中间结果栈) vectorExprTreeNode* expr_tree_build; //用于构建表达式树的栈 size_t num_of_cur_operand 0; string expr w*(v*!(mn-u)-~!^a!b-c*d/ef|ghi)x; //中缀表达式 string::size_type index 0; while (index expr.size()) { mapchar, OperatorInfo::iterator it; if ((it operator_info_list.find(expr[index])) operator_info_list.end() expr[index] ! ( expr[index] ! )) { operand_stack.push_back(expr[index]); expr_tree_build.push_back(new ExprTreeNode(expr[index])); num_of_cur_operand; } else { if (operator_stack.empty() true || expr[index] () { operator_stack.push_back(expr[index]); } else if (expr[index] )) { while (operator_stack.back() ! () { check(operator_stack.back(), num_of_cur_operand, operator_info_list[operator_stack.back()]); buildExprTree(expr_tree_build, operator_stack.back(), operator_info_list[operator_stack.back()]); operand_stack.push_back(operator_stack.back()); operator_stack.pop_back(); if (operator_stack.empty()) { std::cout ERROR:没有与右括号匹配的左括号 endl; exit(-1); } } operator_stack.pop_back(); } else { while (operator_stack.empty() false operator_stack.back() ! ( operator_info_list[operator_stack.back()].priority it-second.priority) { mapchar, OperatorInfo::iterator p operator_info_list.find(operator_stack.back()); if (p-second.priority it-second.priority) { if (it-second.isBinaryOperator false || it-second.isLeftUnion false) { break; } } if (p-second.priority it-second.priority) { check(operator_stack.back(), num_of_cur_operand, p-second); buildExprTree(expr_tree_build, operator_stack.back(), p-second); operand_stack.push_back(operator_stack.back()); operator_stack.pop_back(); } } operator_stack.push_back(expr[index]); } } index; } while (!operator_stack.empty()) { check(operator_stack.back(), num_of_cur_operand, operator_info_list[operator_stack.back()]); buildExprTree(expr_tree_build, operator_stack.back(), operator_info_list[operator_stack.back()]); operand_stack.push_back(operator_stack.back()); operator_stack.pop_back(); } std::cout 后缀表达式为 endl; //输出后缀表达式 for (size_t i 0; i operand_stack.size(); i) { std::cout operand_stack[i]; } std::cout endl; ExprTreeNode* root expr_tree_build.back(); //root为表达式树根节点 std::cout 表达式树的后序遍历结果为:; PostorderTraversal(root); //后序遍历表达式树输出后缀表达式 std::cout endl; }