解析算术表达式.doc

解析算术表达式1后缀式(逆波兰式)六212011293Leave a Comment Written by Blueve 后缀(postfix, 也成逆波兰 reverse Polish)表达式在我们的生活中并不常见，在我们日常中见到的，通常都是中缀(infix)式，例如：3.14 + 15 * (9.2 6.5)这是便于人类理解的表达式，之所以便于人类理解，是因为人从小便接受识别此类表达式的教育，而且这种记号方式将运算符和数字明确的分开，不会产生数字堆叠在一起的混乱情况。但是对于计算机而言，这样的表达式并不好理解，计算机是一种线性读入信息，线性输出信息的工具，人类所通识的中缀式，对于这种规规矩矩按照顺序计算的工具而言，是不容易理解的。你可能一眼就看出来要先算小括号里的表达式，然后算乘法，最后算加法。而计算机直接读入的话，可能会先算3.14 + 15，这自然是荒谬的，而后缀法就为计算机计算表达式提供了一种非常有效的解决方案。这篇文章主要的内容是介绍如何将中缀表达式转换为后缀表达式。说了这么半天，后缀表达式又是什么样子呢？它又有什么样的优势呢？我们现在来看一组对比：中缀式后缀式a + ba b +a + b * ca b c * +(a + b) * ca b + c *后缀表达式为什么会有优势呢？因为计算机线性读入的特征，我们以第二个表达式为例，以：用后缀式，在计算机的计算过程就是： 1. a2. a b3. a b c4. a b c *5. a (b * c) 计算出b * c的值记作x6. a x +7. (a + x) 计算出a + x 的值就是这样一个符合线性读入过程的运算，这样就合理的解决了运算之间优先关系的处理。那么如何将一个中缀式装换为后缀式呢？其实算法很简单，运用之前我介绍过的“栈”就可以轻易达到这个目的，我们使用两个栈，一个是表达式栈，用来存储转换成后缀表达式的结果，一个是运算符栈，用来暂存表达式中的运算符，这个栈满足条件“从栈顶到栈底，运算符的优先级依次下降”，我们以表达式a + b * (c + d) 作为例子，来模拟一下转换的过程：1.读入数字a，存入表达式栈，紧接着读入运算符+，存入运算符栈2.读入数字b，存入表达式栈，紧接着读入运算符*，由于*比+运算优先级高，所以也可以存入运算符栈3.读入左括号(，(具有最高优先级，所以也存入运算符栈，后面的数字c存入表达式栈4.读入运算符+，存入运算符栈，然后读入数字d，存入表达式栈5.读入右括号)，开始弹出运算符栈中的运算符到表达式栈，直到遇到左括号为止6.表达式已经读完了，将运算符栈中的运算符全部弹出到表达式栈，至此后缀表达式已经转换完成！总结下来，基本步骤很明确，就是以下几个步骤：（1）读入，如果是数字，就置入表达式栈，然后重复（1）。如果是运算符继续（2）如果是)，则将运算符栈中直到(之前的运算符都弹入表达式栈，并弹出(。否则继续（3）与运算符栈中的栈顶表达式比较，优先级高的话，置入运算符栈。否则将栈内的低优先级运算符弹入表达式栈，然后将新的运算符置入表达式栈。继续（4）如果所有的字符都已经读入完成，则将运算符栈中的符号全部弹入表达式栈，至此完成转换。否则，回到步骤（1）。有了这样的算法思路，实现起来那就是非常容，易的事情了。下面给出我写的转换代码，需要注意，我的代码没有处理负号这样的情况，而且对于非法的表达式（比如括号不匹配，两个乘号在一起）也没有进行识别，所以在实用性上还是有所欠缺的。代码中通过一点简单的方法使得输入表达式的数字可以是浮点型的，表达式以字符串型栈保存，方便以后转换为数字。以下为代码：?123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108#include #include #include #include using namespace std; /* * 比较运算符的优先级 * 返回高true * 或低false */bool cmpPRI(char a, char b) /构造优先级表 short priList48; priList0= 16; priList( = 1; priList* = 3; priList/= 3; priList+ = 4; priList- = 4; if(priLista priListb) return true; else return false; /* * 将前缀式转化为后缀式 * 读入表达式串及寄存栈 */void E2Postfix(string expr, stack &rExpr) stack opS; /符号 opS.push(0); string:size_type eLen(expr.size(); /记录读入表达式的长度 bool isDigit(false); /记录表达式是否是数字的组成部分 string dTmp; /暂存数字 string oTmp; /暂存符号 /循环读入表达式，并对应入栈 for(int i(0); i eLen; +i) /这里来判断是否读入了一个数字（的一部分） if(isdigit(expri) | expri = .) isDigit = true; else isDigit = false; if(isDigit) dTmp += expri; /表达式中的数字组合暂存 else if(!dTmp.empty() rExpr.push(dTmp); /上一个数字入表达式栈 dTmp = ; if(expri = ) /若为右括号，则向左弹出所有运算符 while(opS.top() != () oTmp = opS.top(); rExpr.push(oTmp); /符号入表达式栈 opS.pop(); /弃用左括号 opS.pop(); else if(cmpPRI(expri, opS.top() | opS.top() = () /如果当前运算符优先级高则入符号栈 opS.push(expri); /符号入运算符栈 else oTmp = opS.top(); rExpr.push(oTmp); /符号入表达式栈 opS.pop(); /对于四则运算而言，如果运算优先级低，则为+或- /可能的话前一个运算符弹出 if(opS.top() oTmp = opS.top(); rExpr.push(oTmp); /符号入表达式栈 opS.pop(); opS.push(expri); /新符号入运算符栈 if(!dTmp.empty() rExpr.push(dTmp); /表达式末尾数字入栈 while(!opS.empty() oTmp = opS.top(); rEx