本文共 1779 字，大约阅读时间需要 5 分钟。

逆波兰表达式求值

1. 判断是数字还是运算符, 如果是数字, 求出数字的值后入栈.

2. 如果是运算符,从栈中出栈两个数字, 用后出栈的数与前出栈的数根据运算符运算, 再把得到的值入栈.

可能这句话不太好理解, 如过先出栈的为num1, 后出栈的是num2, 运算符为减号时, 新的数 num3 = num2 - num1.

#include
   
    using namespace std;string s;stack
    
      s1, s2;int getrank(char c){   	if(c == '*' || c == '/') return 2;	else return 1;}void work(){   	//cin >> s;	int l = s.length();	for(int i = 0; i < l; ++i)	{   		if(s[i]>='0' && s[i] <= '9') s2.push(s[i]);		else if(s[i] == '(') s1.push(s[i]);		else if(s[i]=='+'||s[i]=='-'||s[i]=='*'||s[i]=='/')		{   			if(s1.empty() || s1.top() == '(') s1.push(s[i]);					else if(getrank(s[i]) > getrank(s1.top()))				s1.push(s[i]);			else 			{   				while(!s1.empty() && s1.top() != '(' && getrank(s[i]) <= getrank(s1.top()))				{   					s2.push(s1.top());					s1.pop();				}				if(s1.empty() ||  s1.top() == '(' || getrank(s[i]) > getrank(s1.top()))					s1.push(s[i]);			}		}		else //  s[i] 是 ')' 		{   			while(!s1.empty() && s1.top() != '(') 			{   				s2.push(s1.top());				s1.pop();			}			if(!s1.empty()) s1.pop();// 把 '(' pop掉 		}	}	vector 
     
       v;	while(!s1.empty())	{   		s2.push(s1.top()); 		s1.pop();	}	while(!s2.empty())	{   		v.push_back(s2.top()); 		s2.pop();	}	//for(int i = v.size() - 1; i >= 0; --i)	//cout << v[i] << " "; cout << endl;	// 以上是中缀转后缀	stack 
      
        s3;// 求解逆波兰表达式	for(int i = v.size() - 1; i >= 0; --i)	{   		if(v[i]>='0'&&v[i]<='9') s3.push((double)v[i]-'0');		else		{   			double x = s3.top();s3.pop();			double y = s3.top();s3.pop();			if(v[i]=='+') s3.push(x+y);			else if(v[i]=='-') s3.push(y-x);			else if(v[i]=='*') s3.push(x*y);			else s3.push(y/x);		}		}	printf("%d\n",(int)s3.top());}int main(){   	while(cin >> s) work();	return 0;}// (2+7-8/4)+(7-3+8*2)// 2 7 + 8 4 / - 7 3 - 8 2 * + +// 1+((2+3)*4)-5// 1 2 3 + 4 * + 5 -