3993 - 栈实现表达式求值

4+2*3-10/5#
33*(11-2)#
2*3/2#

8
297
3

提示

栈的应用

C++解答

#include <iostream>
#include <stack>
using namespace std;
string fun1(string s)//中缀转后缀 
{
	stack<char> a;
	string r="";
	for(int i=0;i<s.length()-1;i++)
	{
		 if(s[i]>='0'&&s[i]<='9')
		 {
		 	r+=s[i];
		 	if(s[i+1]=='#'||!(s[i+1]>='0'&&s[i+1]<='9'))//下一个字符不是数字
		 	{
		 		r+=" ";
		 	}
		 }
		 else//非数字 
		 {
			if(s[i]==')')
			{
				while(a.top()!='(')
				{
					r=r+a.top()+" "; 
					a.pop();
				}
				a.pop();//左括号出栈 
			}
			else
			{
				while(!a.empty()&&s[i]!='('&&a.top()!='('&&!(s[i]=='*'&&a.top()=='+')&&!(s[i]=='*'&&a.top()=='-')&&!(s[i]=='/'&&a.top()=='+')&&!(s[i]=='/'&&a.top()=='-'))
		 		{
		 			if(a.top()!='(')
		 			{
		 				r=r+a.top()+" ";
		 			}
					a.pop();
		 		}
				a.push(s[i]);
			}
		 }
	}
	while(!a.empty())
	{
		r=r+a.top()+" ";
		a.pop();
	}
	return r;
}
int fun2(string s)//后缀表达式求值 
{
	stack<int> a;
	int x,y,z=0;
	for(int i=0;i<s.length();i++)
	{
		if(s[i]>='0'&&s[i]<='9')
		{
			z=z*10+s[i]-'0';
			if(i==s.length()-1 || s[i+1]==' ')//下一个字符不是数字 
			{
				a.push(z);
				z=0;
			}	
		}
		else if(s[i]!=' ')
		{
			x=a.top();
			a.pop();
			y=a.top();
			a.pop();
			if(s[i]=='*')
			{
				a.push(y*x);	
			}
			else if(s[i]=='/')
			{
				a.push(y/x);	
			}
			else if(s[i]=='+')
			{
				a.push(y+x);	
			}
			else
			{
				a.push(y-x);	
			}
		}
	}
	return a.top();
}
int main()
{
	string s;
	while(cin>>s)
	{
		string t = fun1(s);
		cout<<fun2(t)<<endl;
	}
	return 0;
}