后缀表达式

题目描述

所谓后缀表达式是指这样的一个表达式：式中不再引用括号，运算符号放在两个运算对象之后，所有计算按运算符号出现的顺序，严格地由左而右新进行（不用考虑运算符的优先级）。

如：$\texttt{3*(5-2)+7}$ 对应的后缀表达式为：$\texttt{3.5.2.-*7.+@}$。在该式中，@ 为表达式的结束符号。. 为操作数的结束符号。

输入格式

输入一行一个字符串 $s$，表示后缀表达式。

输出格式

输出一个整数，表示表达式的值。

样例 #1

样例输入 #1

3.5.2.-*7.+@

样例输出 #1

16

提示

数据保证，$1 \leq |s| \leq 50$，答案和计算过程中的每一个值的绝对值不超过 $10^9$。

题解

思考

利用栈将操作数存储下来，由于不用考虑操作符优先级，于是遇到操作符就进行一次操作，并将完成操作后的操作数压栈，最终栈中只剩下一个操作数，即后缀表达式的运算结果。

代码示例

#include<iostream>
using namespace std;
int main()
{
	char a[55];
	cin >> a;
	int stk[50] = {0};//利用栈储存操作数 
	int top = 0;
	int ans = 0;
	for(int i = 0 ; a[i] != '@'; i ++)
	{
		// 读取操作数并压栈 
		int num = 0;
		while(a[i] >= '0' && a[i] <= '9')
		{
			num = num * 10 + a[i] - '0';
			i ++;
		}
		if(a[i] == '.') stk[top++] = num;
		//读取操作符并计算 
		else if(a[i] == '-')
		{
			int num2 = stk[--top];//减数 
			int num1 = stk[--top];//被减数
			stk[top++] = num1 - num2;  
		}
		else if(a[i] == '+')
		{
			int num2 = stk[--top]; 
			int num1 = stk[--top];
			stk[top++] = num1 + num2; 
		}
		else if(a[i] == '*')
		{
			int num2 = stk[--top]; 
			int num1 = stk[--top];
			stk[top++] = num1 * num2; 
		}
		else if(a[i] == '/')
		{
			int num2 = stk[--top]; //除数 
			int num1 = stk[--top]; //被除数 
			stk[top++] = num1 / num2; 
		}
	}
	ans = stk[0];
	cout << ans << endl; 
	return 0;
}