7-21 求前缀表达式的值 (25 分)

7-21 求前缀表达式的值 (25 分)

传送门：

7-21 求前缀表达式的值 (25 分)

题目要求：

• 算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。前缀表达式指二元运算符位于两个运算数之前，例如2+3*(7-4)+8/4的前缀表达式是：+ + 2 * 3 - 7 4 / 8 4。请设计程序计算前缀表达式的结果值。

输入格式:

• 输入在一行内给出不超过30个字符的前缀表达式，只包含+、-、*、/以及运算数，不同对象（运算数、运算符号）之间以空格分隔。

输出格式:

• 输出前缀表达式的运算结果，保留小数点后1位，或错误信息ERROR。

输入样例：

+ + 2 * 3 - 7 4 / 8 4

输出样例：

13.0

思路重现：

• 前缀表达式的求值：从前缀表达式的最右边开始向左遍历，碰到数值压入栈中，碰到运算符将栈顶的两个元素出栈并进行相应的运算，在运算完之后在压入栈，以便后边的操作。然后通过模拟的方式进行实现代码。

代码实现：

#include<bits/stdc++.h>
using namespace std;
string a[100];
int main()
{
	stack<double> s;
	char c;
	double b,d;
	int i = 0;
	int flag = 0;//标记是否错误 
	while(1)
	{
		cin>>a[i++];
		c = getchar();
		if(c == '\n')
			break;
	}
	i--;
	for(int j = i;j >= 0;j--)
	{
		if(a[j] == "+" || a[j] == "-" || a[j] == "*" || a[j] == "/")
		{
			if(s.size() < 2)//第一个错误点：当出现运算符时，栈元素不足与用来运算。
			{
				flag = 1;
				break;
			}
			b = s.top();
			s.pop();
			d = s.top();
			s.pop();
			if(a[j] == "+")
			{
				s.push(b+d);
			}
			else if(a[j] == "-")
			{
				s.push(b-d);
			}
			else if(a[j] == "*")
			{
				s.push(d*b);
			}
			else if(a[j] == "/")
			{
				if(d == 0)//第二个坑点：除数为0.
				{
					flag = 1;
					break;
				}
				s.push(b/d);
			}
		}
		else 
		{
			stringstream ss;//用string流将string转换成double。
			ss<<a[j];
			ss>>b;
			s.push(b);
		}
	}
	if(s.size()!=1)//第三个坑点：最后输出的时候栈里元素个数多于1。
	{
		flag = 1;
	}
	if(flag)
		cout<<"ERROR";
	else
		printf("%.1f",s.top());
	return 0;
}