【信息学奥赛一本通】第三部分数据结构 --＞第一章栈 1331参考代码

这是我第一次做博客，谢谢。

【1331：【例1-2】后缀表达式的值】

从键盘读入一个后缀表达式（字符串），只含有0-9组成的运算数及加（+）、减（—）、乘（*）、除（/）四种运算符。每个运算数之间用一个空格隔开，不需要判断给你的表达式是否合法。以@作为结束标志。

比如，16–9*(4+3)转换成后缀表达式为：16□9□4□3□+*–，在字符数组A中的形式为：

栈中的变化情况：

运行结果：-47

提示：输入字符串长度小于250，参与运算的整数及结果之绝对值均在2^64范围内，如有除法保证能整除。

【输入】

一个后缀表达式。

【输出】

一个后缀表达式的值。

【输入样例】

16 9 4 3 +*-@

【输出样例】

-47

思路：很简单，将后缀表达式转为中缀即可。

注意事项：题目说是2^64，所以用long long（其实long long是2^62，但用long long是100分）

代码：

#include <bits/stdc++.h>
using namespace std;
stack <long long> s;
int main()
{
	string str;
	getline(cin, str);
	int len = str.length();
	long long x;
	for (int i = 0; i < len - 1; i ++) { 
		x = 0;
		long long a, b;
		if (str[i] == '+') { 
			a = s.top();
			s.pop();
			b = s.top();
			s.pop();
			s.push(a+b);
		}
		else if (str[i] == '-') {
			a = s.top();
			s.pop();
			b = s.top();
			s.pop();
			s.push(b-a);
		}
		else if (str[i] == '*') {
			a = s.top();
			s.pop();
			b = s.top();
			s.pop();
			s.push(a*b);
		}
		else if (str[i] == '/') {
			a = s.top();
			s.pop();
			b = s.top();
			s.pop();
			s.push(b/a);
		}
		while (str[i] >= '0' && str[i] <= '9') {
			x = x*10 + str[i]-'0';
			if (str[i+1] == ' ') {
				s.push(x);
				x = 0;
			}
			i ++;
		}
	}
	printf("%lld\n", s.top());
	return 0;
}