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