【洛谷】P1449 后缀表达式

一、题目信息来源P1449 后缀表达式 - 洛谷题目描述所谓后缀表达式是指这样的一个表达式式中不再引用括号运算符号放在两个运算对象之后所有计算按运算符号出现的顺序严格地由左而右新进行不用考虑运算符的优先级。本题中运算符仅包含 -*/。保证对于 / 运算除数不为 0。特别地其中 / 运算的结果需要向 0 取整即与 C/运算的规则一致。如3*(5-2)7 对应的后缀表达式为3.5.2.-*7.。在该式中为表达式的结束符号。.为操作数的结束符号。输入格式输入一行一个字符串 s表示后缀表达式。输出格式输出一个整数表示表达式的值。说明/提示数据保证1≤∣s∣≤50答案和计算过程中的每一个值的绝对值不超过 109。二、后缀表达式与栈实现我们日常中书写的书写表达式称为中缀表达式例如5*35-15/3.虽然中缀表达式人类看起来一目了然但对于计算机来说解析中缀表达式实际上非常复杂1、括号需要优先处理2、各种运算的优先级问题3、计算机只能顺序读取为此提出了后缀表达式即操作符在操作数后面最简单的一个例子A 操作符 B --- A B 操作符 eg: 3*5 ---3 5 *复杂一点(ab)*c/de按照运算顺序 ab ---ab然后把ab看作一个整体比如看着AA*c/deA*c ---Ac*把A带入abc*再看作一个整体BB/deB/d ---Bd/把B带入abc*d/再看作整体CCeCe---Ce把C带入得到abc*d/e再复杂一点a*b(cd/e)*(f-g)按照运算顺序 d/e ---de/然后把de/看作整体Aa*b(cA)*(f-g)cA---cA把A带入cde/再看作整体Ba*bB*(f-g)f-g ---fg-看作整体Ca*bB*CB*C---BC*把BC带入得到cde/fg-*,看作整体Da*bD,a*b---ab*看作整体EED---ED,把ED带入得到ab*cde/fg-*到这里基本上已经明白如何从中缀表达式转化为后缀表达式但你心中仍有疑问后缀表达式有什么用别急继续看拿最后一个例子来说a*b(cd/e)*(f-g) ab*cde/fg-*后缀表达式从左往右看计算机顺序读取我们现在有个桶子读到第一个操作数a放在桶子里读到第二个操作数b放在桶子里遇到一个操作符*于是把桶子里的两个操作数ab拿出来来执行操作符得到a*b把a*b结果放在桶子里。然后继续读取读到操作数c放在桶子里读到操作数d放在桶子里读到操作数e放在桶子里读到操作符号/把最后两个操作数拿出来计算得到d/e并放回桶子里然后继续读取又遇到操作符号,把最后两个操着数拿出来运算得到cd/e并放回桶子然后继续读取读到操作数f放在桶子里读到操作数g放在桶子里读到操作符号-,把最后两个操作数拿出来运算得到f-g并放回桶子里。然后继续读取又遇到操作符号*把最后两个操作数拿出来运算并放回桶中然后继续读取遇到最后一个操作符号把最后两个操作数拿出来运算并放回桶中。此时桶里最后一个数字就是a*b(cd/e)*(f-g)就是我们的计算结果。这个桶子结构就是我们的栈。三、完整代码using namespace std; #includeiostream #includestring #includestack int calculate(string s){ stackint op; int index 0; int num 0; while(indexs.length()){ if(isdigit(s[index])){ numnum*10s[index]-0; }else if(s[index].){ op.push(num); num 0; }else if(s[index]){ break; }else{ int first,second; second op.top(); op.pop(); first op.top(); op.pop(); switch (s[index]) { case : op.push(firstsecond); break; case -: op.push(first-second); break; case *: op.push(first*second); break; case /: op.push(first/second); break; } } index; } return op.top(); } int main(){ string str; cinstr; int result calculate(str); coutresult; return 1; }