首页 > 代码库 > 表达式的计算（中缀表达式转为后缀表达式或逐步计算）
表达式的计算（中缀表达式转为后缀表达式或逐步计算）
算数表达式的计算，也是很基础的一个问题。花了点时间写了下。
网上很多正确代码。但没有详细说明。虽然不复杂，但是还是写详细点。只有仔细思考过。问题才会在头脑中，觉得简单。
基本有2种方法。
1）中缀表达式转为后缀表达式，是最简洁有力的方法。
2）符合人的计算思路的逐步方法，不推荐使用，只适合锻炼下逻辑能力。
一。中缀表达式转为后缀表达式，是最简洁有力的方法。
//更简洁通用的算法，就是把中缀表达式转换为后缀表达式。后缀表达式：不包含括号，运算符放在两个运算对象的后面。
//一，无括号的n级符号算法。
//如2+3*6-4转化为236*+4-。+号不能防入2和3后面，因为*号更优先。+号必须作用于3*6和2。
//分析：
//创建一个后缀表达式堆，一个临时符号栈。
//读入的数字放入后缀表达式堆。
//读入的符号必须和后面的符号比较，只有优先级更高才能插入到后缀表达式堆后面。
//所以第一个符号一定先入符号栈，等后面符号出来，才能决定栈顶符号是否放入后缀表达式堆。
//因此每次读到运算符，决定的不是这个运算符是否放入后缀表达式，而是决定前一个符号（栈顶符号）的去留。
//1）读入的是数字，直接放入后缀表达式堆
//2）读入的是符号：
// 2。1）如果符号栈为空，动作：放入栈，原因：只有一个符号，必须等待插入数字后，并读起后面一个符号再处理。
// 2。2）如果符号栈非空，且优先级>=栈顶符号，动作：放入栈。原因：栈顶符号，优先级更低，暂时不能放入后缀表达式堆，而刚读的符号也必须再一次等待插入数字后，并和后面一个符号比较再处理（我们并不固定符号优先级别只有2级，）。
// 2。3）如果符号栈非空，且优先级<=栈顶符号,动作，pop栈顶符号，防入后缀表达式堆。新读的符号继续和栈顶符号比较，重复第2）大步骤
// 原因：栈顶符号优先级别高，可以马上放到它左右数字的后面形成后缀表达式。（读入符号前，已经把栈顶的右边数字防入后缀表达式堆）
// 继续比较的原因，可以看作之前插入的栈顶符号，其实是插入了一个临时结果，而此时的栈顶符号，必须和读入的符号，再次争夺临时结果的处理优先级。自己看下2+3*6^5+2，^插入后，*和+争夺6^5就清楚了。
//3）到达表达式结尾。动作：把符号从符号栈，从栈顶依次放入后缀表达式堆。用后缀方法，计算后缀表达式堆。
// 原因：此时符号栈的符号优先级肯定是逐步递增的，否则中途有一个不是递增那么它之前的符号已经进入后缀表达式堆了。
//这里2。3需要再次分析下。2。3和一直和栈顶符号比较，最终会走向2，1，或2。2。最后这个刚读入的符号是一定会入符号栈的。
//所以，所有的符号和数字都在后缀表达式堆或临时符号栈。而第3）又会把所有最终留下的符号放入后缀表达式堆。
//二。有括号的算法。
//如（2+3）*6-4转化为23+6*
//分析：
//读入的符号碰到（，因为（）内其实是一个子表达式。必须优先处理。也就是把（）内的数字和符号转化为中缀表达式，防入到后缀表达式堆后（相当于放入了一个临时结果）
//栈顶的符号再和）之后的符号比较优先级。
//1）读入的是数字，直接放入后缀表达式堆
//2）读入的是运算符号：
// 2。1）如果符号栈为空，动作：放入栈，原因：只有一个符号，必须等待插入数字后，并读起后面一个符号再处理。
// 2。2）如果符号栈非空，且优先级>=栈顶符号，动作：放入栈。原因：栈顶符号，优先级更低，暂时不能放入后缀表达式堆，而刚读的符号也必须再一次等待插入数字后，并和后面一个符号比较再处理（我们并不固定符号优先级别只有2级，）。
// 2。3）如果符号栈非空，且优先级<=栈顶符号,动作，pop栈顶符号，防入后缀表达式堆。新读的符号继续和栈顶符号比较，重复第2）大步骤。
// 原因：栈顶符号优先级别高，可以马上放到它左右数字的后面形成后缀表达式。（读入符号前，已经把栈顶的右边数字防入后缀表达式堆）
// 继续比较的原因，可以看作之前插入的栈顶符号，其实是插入了一个临时结果，而此时的栈顶符号，必须和读入的符号，再次争夺临时结果的处理优先级。自己看下2+3*6^5+2，^插入后，*和+争夺6^5就清楚了。
// 2。4）如果符号栈非空，且符号是（，动作，新符号入栈，原因：（屏蔽了之前符号，（后的符号必须和之后的符号比较。
// 2。5）如果符号栈非空，且符号是），不可能存在，因为4）会保证成队消除（），）没有入栈的可能。
//3)读入的是（，动作：（入栈，原因，栈顶符号，必须等待（）括号内全部放入后缀表达式堆后，再和）之后的符号比较。可以看成（比任何符号更优先。
//4）读入的是），动作，一直插入栈顶符号到后缀表达式堆，直到碰到（，并pop掉（。
// 原因：我们必须把（）内的符号和数字全部处理完，下一步才能继续让前括号（之前的悬而未决的符号和后括号）后面的符号比较。
// 为什么一直插入符号就可以，因为此时符号栈最后的前括号（之后的符号优先级肯定是逐步递增的，道理和之前的算法，第3）是一样。
写到最后发现不需要用队列来储存后缀表达式，用数组就足够了。有空再修改下。（）2个括号的判断，很多算法都是把他们放入运算符号中，一起去比较优先级别。
其实自己发现，一开始还是分开分析。更容易理清思路。算法出来后，才考虑简化流程，其实没必要简化流程。仅仅少写2条判断，而让人不容易理解，教程文章的话，自己感觉没必要。
二。逐步计算方法。
//算术表达式的求解。
//1，无括号
//遇到符号，不能决定马上进行运算。必须和右边的符号进行优先级别对比。更高或者一样（左结合规）才能进行运算。
//所以思路可以2个栈，一个数字栈，一个符号栈。（先假设运算表达式本身已合法）
//从左到右读出数字或符号。（表达式的书写和运算顺序决定，4-3，不能解释为3-4），
//算法描述。
//为了清晰描述过程。分为4个步骤。（用状态图来描述的话会更直观，3个状态就可以了）
//1，读第一个数字到数字栈。
//2，读一个符号，再读一个数字。根据情况进行处理。，
//3，重复第二步骤。
//4，到达表达式结尾。
// 结论：数字栈数量至少为一，并且数字栈的数量比符号崭数量多一，并且符号栈的元素，从栈顶优先级依次降低，直到栈底。那么依次取符号栈栈顶，和数字栈栈顶二次，运算结果防入栈顶。直到结束，可以求到正确结果。
//处理动作。
//1，第一步简单，数字入数字栈，无任何运算，
//2，
// 1) 新符号优级 空 空栈顶，栈顶空。那么符号入符号栈。数字入数字栈。等待处理。
// 2）新符号优级 <= 栈顶符号，那么栈顶符号可以和数字栈的前2个数字进行运算。所以数字栈pop 2个数字，计算结果放入栈顶，读出的符号和数字继续再进行第二步骤。（相比刚读出的符号，栈顶符号是更早的左边的运算符号）
// 3）新符号优级 > 栈顶符号，那么符号入崭，继续和下一符号对比，数字也入数字栈。（对于+-*/，只有2级，那么必定是*/，可以确定运算了，用刚读的符号对刚读的数字和栈顶数字运算，但是为了通用性，不假定只有2级）
//4，到达表达式结尾。结论：数字栈数量至少为一，并且数字栈的数量比符号崭数量多一，并且符号栈的元素，从栈顶优先级依次降低，直到栈底。那么依次取符号栈栈顶，和数字栈栈顶二次，运算结果防入栈顶。直到结束，可以求到正确结果。
// 证明思路正确，必须证明经过各种情况，第4步的结论成立。
//
// 1)只有第一个步骤。那么整个表达式，只有一个数字。满足结论。
// 2)假如经过第一步骤重复第二步骤。那么只要证明每个步骤都满足结论。
// 1，
// 新符号优级 空 空栈顶：
// 数字栈数字数量+1，符号数量+1。
// 若之前满足结论，那么根据结论，符号站空，必定数字栈只有一个元素。现在都+1，而且只有一个运算符号，那么也满足结论。
// 2，
// 新符号优级 <= 栈顶符号：
// 数字栈数字数量-1（-2，+1），符号数量-1（-1），且运算逻辑正确。注意新读的符号和数字并未防入各自的栈中。
// 若之前满足结论，那么现在符号数量仍然比数字符号少1。栈顶少一个符号，因假定之前满足结论，那栈内之前存在的符号肯定满足自顶而下的优先级。那么也满足结论。
// 3，新符号优级 > 栈顶符号
// 数字栈数字数量+1，符号数量+1。
// 若之前满足结论，现在符号和数字都+1，且新栈顶符号优先级大于之前栈顶。所以满足结论。
// 另外第二步骤的第2种情况，数字和符号并未入栈，必须证明第2步骤会进入第1和第3步骤。这样，表达式所有符号和数字，或临时结果都在2个栈中。结论已经可以支持正确计算，证明这个余下问题，就结束了。
// 1）第2种情况会进行计算，并消除崭顶符号。如果一直新符号优级 <= 栈顶符号，那么会导致崭顶空。就进入第一种情况。
// 2）如果新符号优级 > 栈顶符号。直接进入第3种情况。到此表达式所有符号和数字，或临时结果都在2个栈中。
//算法描述：
//设置2个栈，数字栈和符号栈。
//依次读出一个数字或符号。算法的控制条件，第一个必须为数字，这次取得的必须和上次取的互相不同。一次数据，一次符号。结尾一定是数字。
//一步骤：如果是数字，那么push到数字栈。
//二步骤：如果是符号。
// 1。如果符号栈为空，push新符号到符号栈。
// 2。如果新符号优级 <= 栈顶符号。pop出数字栈2个数字,pop出栈顶符号，并进行计算，结果再push到数字栈。新符号返回再次执行二步骤。(栈顶符号确定可以运算，)
// 3。如果新符号优级 > 栈顶符号。新符号入栈。（栈顶符号不能运算，新符号又必须等待和后面符号再对比）
//三步骤：到达表达式结尾。
// 依次取符号栈栈顶，和数字栈栈顶二次，运算结果防入栈顶。直到结束，可以求到正确结果。
//到达表达式结尾时，有2个结论。
// 结论1:数字栈数据数量-符号栈符号数量=1，并且数字栈数量>=1。
// 结论2:符号栈的符号，优先级从栈顶到栈底依次降低。那么依次取符号栈栈顶，和数字栈栈顶二次，运算结果防入栈顶。直到结束，可以求到正确结果。
//算法证明：
// 必须证明结论1，2成立，才能证明算法正确。
// 结论1:数字栈数据数量-符号栈符号数量=1，并且数字栈数量>=1。
// 证明：算法的控制条件：数字开头，数字结尾，数字和符号相继读取。保证了数字总量比符号总量大1。
// 一步骤：总量不变。
// 二步骤，1情况：总量不变。
// 二步骤，2情况：数字栈pop2次。push一次结果 -1（-2+1），符号栈pop一次（-1）。数字栈和符号栈数量都-1。满足结论。
// 二步骤，3情况：总量不变。
// 结论2：符号栈的符号，优先级从栈顶到栈底依次降低。
// 证明：二步骤，1情况，只有一个符号，满足条件。
// 二步骤，2情况：如果之前满足优先级从栈顶到栈底依次降低，pop一个符号后，也一定满足结论。
// 二步骤，3情况：如果之前满足优先级从栈顶到栈底依次降低，push一个比栈顶高优先符号，也满足结论。
// 必须注意到所有的证明的前提是符号和数字要全部入过栈。但是二步骤2情况，符号并没有入栈，而是再次执行二步骤。所以必须确定二步骤2情况，一定会转入到二步骤其他分支情况。
// 1）如果一直新符号优级 <= 栈顶符号，那么会导致崭顶空。就进入第一种情况。
// 2）如果新符号优级 > 栈顶符号。直接进入第3种情况。
//带括号，括号内也是一个表达式。括号内的表达式要优先计算。
//所以碰到（，因（并非运算符号，本来无法比较运算优先级别，但暗示了前面符号暂时无法处理。必须等（）内计算出结果，所以可以看成（优先于其他运算符号，（放入符号栈。
//另一方面，当碰到），必须把（之前的符号处理运算完。
//为什么可以处理完。因为（），挡住了前后的符号，只需要比较括号内的符号优先级别。（）内的符号，都高于（）外的符号，另外一个角度看，可以看成括号内的符号高于两边的括号符（）
//这样得到的数字入数字栈，并无条件清理掉成对的（）。这样就（）的处理最终，看成仅仅插入了一个数字而已。
//如果是（）嵌套。上面的思路步骤也是一样。
//分析完毕。算法如下。。
//如果是(,
// 1）符号栈为空，说明一定是表达式头，否则符号栈一定有符号。那么（直接入栈。
// 2）符号栈不为空，因要优先处理（）内的表达式，栈顶符号级别低于（，所以（入栈，并等待和）成队消除。
//如果是），
// 1）栈顶元素为不为（，那么可以断定。（）之间的符号优先级是递减的。可以循环以下动作：直接取一符号，取2数字，计算结果，结果入栈，直至碰到（符号。
// 为什么可以断定（）之间的符号优先级是递减的。请参考之前结论2。（）内子表达式的算法是依据之前算法，结论也必定满足结论2。
// 2）栈顶元素为（，那么直接成对消除。
//和之前的不带括号的算法，结合一下，算法如下，
//二步骤：如果是符号。
// 1。如果符号栈为空，push新符号到符号栈。
// 2。如果新符号优级 <= 栈顶符号。pop出数字栈2个数字,pop出栈顶符号，并进行计算，结果再push到数字栈。新符号返回再次执行二步骤。(栈顶符号确定可以运算，)
// 3。如果新符号优级 > 栈顶符号。新符号入栈。（栈顶符号不能运算，新符号又必须等待和后面符号再对比）
// 4。如果栈顶符号是（，符号入栈。
// 5。如果栈顶是），不可能有这种情况。），一出现就会强制运算，并成对消除。
// 6。如果是(，（入栈。
// 7。如果是），栈顶不为（，循环以下动作：直接取一符号，取2数字，计算结果，结果入数字栈。
// 8。如果是），栈顶为（。成对消除（）。
//第8种情况稍微分析下，看看以上算法是否连续，当遇到第8种情况。下一个元素必定是运算符号或符号）。
//1）如果下一符号是运算符号，因为（）之内的表达式，已经计算完毕，结果已经放入数字栈。所以取得的运算符号，可以和栈顶符号，继续比较优先级。所以执行1~4运算算法，无错。
//2）如果下一符号是）。那么应该要求再次计算出（）内的数值，那么执行7~8步骤，无错。
//所以，算法应该无错。
express.h
#ifndef EXPRESS_H_INCLUDED#define EXPRESS_H_INCLUDED#include "string"#include "stack"#include "queue"#include <sstream>using namespace std;struct expEle{public: char operatorChar; float number; bool isNumber;};class express{public: express(const string&); float Calculate(); float getResult();private: string expressstr; float result; express(); string getEle(int); inline int isnum(const string&); int checkLevel(const char);};express::express(const string& _express):expressstr(_express){}float express::Calculate(){ int position=0; queue<expEle> queue_exp; stack<char> stack_operator; while(position!=expressstr.size()) { string ele=getEle(position); expEle Current_ele; if(isnum(ele)==1) { stringstream ss; ss<<ele; ss>>Current_ele.number; Current_ele.isNumber=true; Current_ele.operatorChar=‘\0‘; queue_exp.push(Current_ele); position+=ele.size(); } else if(isnum(ele)==0 && ele!="(" && ele!=")") { char newOperator=*ele.c_str(); Current_ele.isNumber=false; Current_ele.operatorChar=newOperator; Current_ele.number=0; if(stack_operator.size()==0) { stack_operator.push(newOperator); position+=ele.size(); } else { char preOperater=stack_operator.top(); if(checkLevel(newOperator)>checkLevel(preOperater) || preOperater==‘(‘) { stack_operator.push(newOperator); position+=ele.size(); } else { char topOperator=stack_operator.top(); stack_operator.pop(); expEle topOpe; topOpe.isNumber=false; topOpe.operatorChar=topOperator; queue_exp.push(topOpe); } } } else if(ele=="(") { char newOperator=*ele.c_str(); Current_ele.isNumber=false; Current_ele.operatorChar=newOperator; Current_ele.number=0; stack_operator.push(newOperator); position+=ele.size(); } else if(ele==")") { while(stack_operator.top()!=‘(‘) { expEle tmpEle; tmpEle.isNumber=false; tmpEle.operatorChar=stack_operator.top(); stack_operator.pop(); queue_exp.push(tmpEle); } stack_operator.pop();//清除（ position+=ele.size();//清除） } else { cout<<"error:invalid input."<<endl; return 0; } } while(stack_operator.size()!=0) { expEle tmpEle; tmpEle.isNumber=false; tmpEle.operatorChar=stack_operator.top(); stack_operator.pop(); queue_exp.push(tmpEle); } while(queue_exp.size()!=0) { expEle tmpele=(expEle)queue_exp.front(); if(tmpele.isNumber) { cout<< tmpele.number; } else { cout<< tmpele.operatorChar; } queue_exp.pop(); }}float express::getResult(){ int searchedLen=0; stack<float> stack_float; stack<char> stack_operator; while(searchedLen!=expressstr.size()) { string ele=getEle(searchedLen); if(isnum(ele)==1) { stringstream ss; float float1; ss<<ele; ss>>float1; stack_float.push(float1); searchedLen+=ele.size(); } else if(isnum(ele)==0) { char newOperator=*ele.c_str(); if(stack_operator.size()==0) { stack_operator.push(newOperator); searchedLen+=ele.size(); } else { char preOperater=stack_operator.top(); if(checkLevel(newOperator)>checkLevel(preOperater)) { stack_operator.push(newOperator); searchedLen+=ele.size(); } else { float tempop1=stack_float.top(); stack_float.pop(); float tempop2=stack_float.top(); stack_float.pop(); stack_operator.pop(); float tempResult; switch(preOperater) { case ‘+‘: tempResult=tempop2+tempop1; break; case ‘-‘: tempResult=tempop2-tempop1; break; case ‘*‘: tempResult=tempop2*tempop1; break; case ‘/‘: tempResult=tempop2/tempop1; break; } stack_float.push(tempResult); } } } else { cout<<"error:invalid input."<<endl; return 0; } } while(stack_operator.size()>0) { char tempope=stack_operator.top(); stack_operator.pop(); float tempop1=stack_float.top(); stack_float.pop(); float tempop2=stack_float.top(); stack_float.pop(); float tempResult; switch(tempope) { case ‘+‘: tempResult=tempop2+tempop1; break; case ‘-‘: tempResult=tempop2-tempop1; break; case ‘*‘: tempResult=tempop2*tempop1; break; case ‘/‘: tempResult=tempop2/tempop1; break; } stack_float.push(tempResult); } return stack_float.top();}inline int express::isnum(const string& _ele){ if(_ele=="+" ||_ele=="-"||_ele=="*"||_ele=="/"||_ele=="("||_ele==")") { return 0; } else { return 1; }}inline int express::checkLevel(const char _operator){ if(_operator==‘+‘||_operator==‘-‘) { return 1; } else if(_operator==‘*‘||_operator==‘/‘) { return 2; } else { return -1; }}string express::getEle(int index){ string temp=expressstr.substr(index,1); return temp;}//算术表达式的求解。 //1，无括号 //遇到符号，不能决定马上进行运算。必须和右边的符号进行优先级别对比。更高或者一样（左结合规）才能进行运算。 //所以思路可以2个栈，一个数字栈，一个符号栈。（先假设运算表达式本身已合法） //从左到右读出数字或符号。（表达式的书写和运算顺序决定，4-3，不能解释为3-4）， //算法描述。 //为了清晰描述过程。分为4个步骤。（用状态图来描述的话会更直观，3个状态就可以了） //1，读第一个数字到数字栈。 //2，读一个符号，再读一个数字。根据情况进行处理。， //3，重复第二步骤。 //4，到达表达式结尾。 // 结论：数字栈数量至少为一，并且数字栈的数量比符号崭数量多一，并且符号栈的元素，从栈顶优先级依次降低，直到栈底。那么依次取符号栈栈顶，和数字栈栈顶二次，运算结果防入栈顶。直到结束，可以求到正确结果。 //处理动作。 //1，第一步简单，数字入数字栈，无任何运算， //2， // 1) 新符号优级 空 空栈顶，栈顶空。那么符号入符号栈。数字入数字栈。等待处理。 // 2）新符号优级 <= 栈顶符号，那么栈顶符号可以和数字栈的前2个数字进行运算。所以数字栈pop 2个数字，计算结果放入栈顶，读出的符号和数字继续再进行第二步骤。（相比刚读出的符号，栈顶符号是更早的左边的运算符号） // 3）新符号优级 > 栈顶符号，那么符号入崭，继续和下一符号对比，数字也入数字栈。（对于+-*/，只有2级，那么必定是*/，可以确定运算了，用刚读的符号对刚读的数字和栈顶数字运算，但是为了通用性，不假定只有2级） //4，到达表达式结尾。结论：数字栈数量至少为一，并且数字栈的数量比符号崭数量多一，并且符号栈的元素，从栈顶优先级依次降低，直到栈底。那么依次取符号栈栈顶，和数字栈栈顶二次，运算结果防入栈顶。直到结束，可以求到正确结果。 // 证明思路正确，必须证明经过各种情况，第4步的结论成立。 // // 1)只有第一个步骤。那么整个表达式，只有一个数字。满足结论。 // 2)假如经过第一步骤重复第二步骤。那么只要证明每个步骤都满足结论。 // 1， // 新符号优级 空 空栈顶： // 数字栈数字数量+1，符号数量+1。 // 若之前满足结论，那么根据结论，符号站空，必定数字栈只有一个元素。现在都+1，而且只有一个运算符号，那么也满足结论。 // 2， // 新符号优级 <= 栈顶符号： // 数字栈数字数量-1（-2，+1），符号数量-1（-1），且运算逻辑正确。注意新读的符号和数字并未防入各自的栈中。 // 若之前满足结论，那么现在符号数量仍然比数字符号少1。栈顶少一个符号，因假定之前满足结论，那栈内之前存在的符号肯定满足自顶而下的优先级。那么也满足结论。 // 3，新符号优级 > 栈顶符号 // 数字栈数字数量+1，符号数量+1。 // 若之前满足结论，现在符号和数字都+1，且新栈顶符号优先级大于之前栈顶。所以满足结论。 // 另外第二步骤的第2种情况，数字和符号并未入栈，必须证明第2步骤会进入第1和第3步骤。这样，表达式所有符号和数字，或临时结果都在2个栈中。结论已经可以支持正确计算，证明这个余下问题，就结束了。 // 1）第2种情况会进行计算，并消除崭顶符号。如果一直新符号优级 <= 栈顶符号，那么会导致崭顶空。就进入第一种情况。 // 2）如果新符号优级 > 栈顶符号。直接进入第3种情况。到此表达式所有符号和数字，或临时结果都在2个栈中。 //算法描述： //设置2个栈，数字栈和符号栈。 //依次读出一个数字或符号。算法的控制条件，第一个必须为数字，这次取得的必须和上次取的互相不同。一次数据，一次符号。结尾一定是数字。 //一步骤：如果是数字，那么push到数字栈。 //二步骤：如果是符号。 // 1。如果符号栈为空，push新符号到符号栈。 // 2。如果新符号优级 <= 栈顶符号。pop出数字栈2个数字,pop出栈顶符号，并进行计算，结果再push到数字栈。新符号返回再次执行二步骤。(栈顶符号确定可以运算，) // 3。如果新符号优级 > 栈顶符号。新符号入栈。（栈顶符号不能运算，新符号又必须等待和后面符号再对比） //三步骤：到达表达式结尾。 // 依次取符号栈栈顶，和数字栈栈顶二次，运算结果防入栈顶。直到结束，可以求到正确结果。 //到达表达式结尾时，有2个结论。 // 结论1:数字栈数据数量-符号栈符号数量=1，并且数字栈数量>=1。 // 结论2:符号栈的符号，优先级从栈顶到栈底依次降低。那么依次取符号栈栈顶，和数字栈栈顶二次，运算结果防入栈顶。直到结束，可以求到正确结果。 //算法证明： // 必须证明结论1，2成立，才能证明算法正确。 // 结论1:数字栈数据数量-符号栈符号数量=1，并且数字栈数量>=1。 // 证明：算法的控制条件：数字开头，数字结尾，数字和符号相继读取。保证了数字总量比符号总量大1。 // 一步骤：总量不变。 // 二步骤，1情况：总量不变。 // 二步骤，2情况：数字栈pop2次。push一次结果 -1（-2+1），符号栈pop一次（-1）。数字栈和符号栈数量都-1。满足结论。 // 二步骤，3情况：总量不变。 // 结论2：符号栈的符号，优先级从栈顶到栈底依次降低。 // 证明：二步骤，1情况，只有一个符号，满足条件。 // 二步骤，2情况：如果之前满足优先级从栈顶到栈底依次降低，pop一个符号后，也一定满足结论。 // 二步骤，3情况：如果之前满足优先级从栈顶到栈底依次降低，push一个比栈顶高优先符号，也满足结论。 // 必须注意到所有的证明的前提是符号和数字要全部入过栈。但是二步骤2情况，符号并没有入栈，而是再次执行二步骤。所以必须确定二步骤2情况，一定会转入到二步骤其他分支情况。 // 1）如果一直新符号优级 <= 栈顶符号，那么会导致崭顶空。就进入第一种情况。 // 2）如果新符号优级 > 栈顶符号。直接进入第3种情况。 //带括号，括号内也是一个表达式。括号内的表达式要优先计算。 //所以碰到（，因（并非运算符号，本来无法比较运算优先级别，但暗示了前面符号暂时无法处理。必须等（）内计算出结果，所以可以看成（优先于其他运算符号，（放入符号栈。 //另一方面，当碰到），必须把（之前的符号处理运算完。 //为什么可以处理完。因为（），挡住了前后的符号，只需要比较括号内的符号优先级别。（）内的符号，都高于（）外的符号，另外一个角度看，可以看成括号内的符号高于两边的括号符（） //这样得到的数字入数字栈，并无条件清理掉成对的（）。这样就（）的处理最终，看成仅仅插入了一个数字而已。 //如果是（）嵌套。上面的思路步骤也是一样。 //分析完毕。算法如下。。 //如果是(, // 1）符号栈为空，说明一定是表达式头，否则符号栈一定有符号。那么（直接入栈。 // 2）符号栈不为空，因要优先处理（）内的表达式，栈顶符号级别低于（，所以（入栈，并等待和）成队消除。 //如果是）， // 1）栈顶元素为不为（，那么可以断定。（）之间的符号优先级是递减的。可以循环以下动作：直接取一符号，取2数字，计算结果，结果入栈，直至碰到（符号。 // 为什么可以断定（）之间的符号优先级是递减的。请参考之前结论2。（）内子表达式的算法是依据之前算法，结论也必定满足结论2。 // 2）栈顶元素为（，那么直接成对消除。 //和之前的不带括号的算法，结合一下，算法如下， //二步骤：如果是符号。 // 1。如果符号栈为空，push新符号到符号栈。 // 2。如果新符号优级 <= 栈顶符号。pop出数字栈2个数字,pop出栈顶符号，并进行计算，结果再push到数字栈。新符号返回再次执行二步骤。(栈顶符号确定可以运算，) // 3。如果新符号优级 > 栈顶符号。新符号入栈。（栈顶符号不能运算，新符号又必须等待和后面符号再对比） // 4。如果栈顶符号是（，符号入栈。 // 5。如果栈顶是），不可能有这种情况。），一出现就会强制运算，并成对消除。 // 6。如果是(，（入栈。 // 7。如果是），栈顶不为（，循环以下动作：直接取一符号，取2数字，计算结果，结果入数字栈。 // 8。如果是），栈顶为（。成对消除（）。 //第8种情况稍微分析下，看看以上算法是否连续，当遇到第8种情况。下一个元素必定是运算符号或符号）。 //1）如果下一符号是运算符号，因为（）之内的表达式，已经计算完毕，结果已经放入数字栈。所以取得的运算符号，可以和栈顶符号，继续比较优先级。所以执行1~4运算算法，无错。 //2）如果下一符号是）。那么应该要求再次计算出（）内的数值，那么执行7~8步骤，无错。 //所以，算法应该无错。 //还有一种更简洁通用的算法，就是把中缀表达式转换为后缀表达式。后缀表达式：不包含括号，运算符放在两个运算对象的后面。 //一，无括号的n级符号算法。 //如2+3*6-4转化为236*+4-。+号不能防入2和3后面，因为*号更优先。+号必须作用于3*6和2。 //分析： //创建一个后缀表达式堆，一个临时符号栈。 //读入的数字放入后缀表达式堆。 //读入的符号必须和后面的符号比较，只有优先级更高才能插入到后缀表达式堆后面。 //所以第一个符号一定先入符号栈，等后面符号出来，才能决定栈顶符号是否放入后缀表达式堆。 //因此每次读到运算符，决定的不是这个运算符是否放入后缀表达式，而是决定前一个符号（栈顶符号）的去留。 //1）读入的是数字，直接放入后缀表达式堆 //2）读入的是符号： // 2。1）如果符号栈为空，动作：放入栈，原因：只有一个符号，必须等待插入数字后，并读起后面一个符号再处理。 // 2。2）如果符号栈非空，且优先级>=栈顶符号，动作：放入栈。原因：栈顶符号，优先级更低，暂时不能放入后缀表达式堆，而刚读的符号也必须再一次等待插入数字后，并和后面一个符号比较再处理（我们并不固定符号优先级别只有2级，）。 // 2。3）如果符号栈非空，且优先级<=栈顶符号,动作，pop栈顶符号，防入后缀表达式堆。新读的符号继续和栈顶符号比较，重复第2）大步骤 // 原因：栈顶符号优先级别高，可以马上放到它左右数字的后面形成后缀表达式。（读入符号前，已经把栈顶的右边数字防入后缀表达式堆） // 继续比较的原因，可以看作之前插入的栈顶符号，其实是插入了一个临时结果，而此时的栈顶符号，必须和读入的符号，再次争夺临时结果的处理优先级。自己看下2+3*6^5+2，^插入后，*和+争夺6^5就清楚了。 //3）到达表达式结尾。动作：把符号从符号栈，从栈顶依次放入后缀表达式堆。用后缀方法，计算后缀表达式堆。 // 原因：此时符号栈的符号优先级肯定是逐步递增的，否则中途有一个不是递增那么它之前的符号已经进入后缀表达式堆了。 //这里2。3需要再次分析下。2。3和一直和栈顶符号比较，最终会走向2，1，或2。2。最后这个刚读入的符号是一定会入符号栈的。 //所以，所有的符号和数字都在后缀表达式堆或临时符号栈。而第3）又会把所有最终留下的符号放入后缀表达式堆。 //二。有括号的算法。 //如（2+3）*6-4转化为23+6* //分析： //读入的符号碰到（，因为（）内其实是一个子表达式。必须优先处理。也就是把（）内的数字和符号转化为中缀表达式，防入到后缀表达式堆后（相当于放入了一个临时结果） //栈顶的符号再和）之后的符号比较优先级。 //1）读入的是数字，直接放入后缀表达式堆 //2）读入的是运算符号： // 2。1）如果符号栈为空，动作：放入栈，原因：只有一个符号，必须等待插入数字后，并读起后面一个符号再处理。 // 2。2）如果符号栈非空，且优先级>=栈顶符号，动作：放入栈。原因：栈顶符号，优先级更低，暂时不能放入后缀表达式堆，而刚读的符号也必须再一次等待插入数字后，并和后面一个符号比较再处理（我们并不固定符号优先级别只有2级，）。 // 2。3）如果符号栈非空，且优先级<=栈顶符号,动作，pop栈顶符号，防入后缀表达式堆。新读的符号继续和栈顶符号比较，重复第2）大步骤。 // 原因：栈顶符号优先级别高，可以马上放到它左右数字的后面形成后缀表达式。（读入符号前，已经把栈顶的右边数字防入后缀表达式堆） // 继续比较的原因，可以看作之前插入的栈顶符号，其实是插入了一个临时结果，而此时的栈顶符号，必须和读入的符号，再次争夺临时结果的处理优先级。自己看下2+3*6^5+2，^插入后，*和+争夺6^5就清楚了。 // 2。4）如果符号栈非空，且符号是（，动作，新符号入栈，原因：（屏蔽了之前符号，（后的符号必须和之后的符号比较。 // 2。5）如果符号栈非空，且符号是），不可能存在，因为4）会保证成队消除（），）没有入栈的可能。 //3)读入的是（，动作：（入栈，原因，栈顶符号，必须等待（）括号内全部放入后缀表达式堆后，再和）之后的符号比较。可以看成（比任何符号更优先。 //4）读入的是），动作，一直插入栈顶符号到后缀表达式堆，直到碰到（，并pop掉（。 // 原因：我们必须把（）内的符号和数字全部处理完，下一步才能继续让前括号（之前的悬而未决的符号和后括号）后面的符号比较。 // 为什么一直插入符号就可以，因为此时符号栈最后的前括号（之后的符号优先级肯定是逐步递增的，道理和之前的算法，第3）是一样。//2+3*6^5+2；//#endif // EXPRESS_H_INCLUDED
main.cpp
#include <iostream>#include <vector>#include "express.h"using namespace std;void mianExpress();int main(){ mianExpress(); //mainMyVector2(); //mainString(); //mainMyVector(); return 0;}void mianExpress(){ string sexpress="3+2*(4-(5+1)+2*2)/3"; express a(sexpress); a.Calculate();}
表达式的计算（中缀表达式转为后缀表达式或逐步计算）