表达式求值（牛客）

题目描述：

给定一个字符串描述的算术表达式，计算出结果值。

输入字符串长度不超过100，合法的字符包括”+, -, *, /, (, )”，”0-9”，字符串内容的合法性及表达式语法的合法性由做题者检查。本题目只涉及整型计算。

输入描述：输入算术表达式（中缀表达式）

400+5

输出描述：计算出结果值

405

做题思路：

将输入的中缀表达式，转换为对应的后缀表达式进行计算

中缀表达式：5+4*6/2+3+(4*5)/5

对应的后缀表达式：5 4 6 * 2 / 3 + 4 5 * 5 / +

中缀表达式转为后缀表达式：

设置一个空栈S1

1.遇到操作数直接输出（输出的含义是指追加到当前后缀表达式后面）

2.栈为空时，遇到运算符，直接入栈

3.遇到左括号时，直接入栈

4.遇到右括号时，如果栈顶的操作符不为左括号，一直出栈，并将出栈的操作符输出。当栈顶的操作符是左括号时，将左括号出栈， 停止本步骤。

5.遇到+-*/运算符op时，如果（栈非空 并且 栈顶操作符的优先级大于等于op时）一直将出栈，并将出栈的操作符输出。当（不满足栈非空 并且 栈顶操作符的优先级大于等于op）时，将op入栈

(栈非空 并且 栈顶操作符的优先级大于等于op时 指的是 满足加减优先级大于等于加减,乘除优先级大于等于加减乘除的情况，其他情况均视为不满足)

6.将栈中所有元素以此出栈输出

利用后缀表达式计算结果：

设置一个空栈S2

顺序扫描后缀表达式S1的每一项，然后根据当前项的类型做出相应的操作

1.如果当前项是操作数：将其压入栈S2中

2.如果当前项是操作符op：从S2弹出栈顶Y，在弹出栈顶X，计算 X<op>Y 并将结果压入栈 S2

当S1扫描结束，S2的栈顶元素值即为表达式的结果

注意事项：

#include<cstdlib>
string s;
int num = atoi(s.c_str());

#incldue<stack>
stack<char> s;
char c = s.top();
s.push('a');
s.pop(); //返回值是void

#include<cctype>
char c;
isdigit(c);
isalpha(c);

AC代码：

#include<iostream>
#include<cctype>
#include<vector>
#include<stack>
#include<string>
#include<cstdlib>

using namespace std;

bool Cmppriority(char s,char c); //比较操作符的优先级
vector<string> sTrans(string &str);//将中缀表达式转换为后缀表达式 
int Calculate(vector<string> res);//根据后缀表达式计算结果
 
int main()
{
	string str;
	cin >> str;
	
	vector<string> res = sTrans(str); 
	int result = Calculate(res);
	
	cout<<result<<endl;
	
	return 0;
} 

bool Cmppriority(char s,char c)
{
	if( (c=='*'||c=='/')&&(s=='*'||s=='/') ){
		return true;
	}
	if( (c=='+'||c=='-')&&(s=='+'||s=='-'||s=='*'||s=='/')){
		return true;
	}
	return false;
}
vector<string> sTrans(string &str)
{
	vector<string> result; //记录后缀表达式 
	stack<char> s;  //用作中间栈,调整符号在后缀表达式中的位置
	string temp; 
	
	for(int i=0; i<str.size(); i++){
		if( isdigit(str[i]) ){  //是一个操作数 
			temp="";
			while( i<str.size()&&isdigit(str[i]) ){
				temp += str[i];
				++i;
			}  
			i--;
			result.push_back(temp); //如果是操作符直接入栈到result
		}else{  //是一个操作符 
			if( s.empty() ){  //栈为空时操作符直接入栈到stack  
				s.push(str[i]);
			}else{
				if( str[i]=='(' ){
					s.push(str[i]);
				}else{
					if( str[i]==')' ){
						while( s.top()!='(' ){
							temp = "";
							temp += s.top();
							result.push_back(temp); //stack出栈 并 入栈到后缀表达式 
							s.pop();
						}
						s.pop(); //将左括号出栈 
					}else{  //遇到+-*/ 
						while( !s.empty()&&Cmppriority(s.top(),str[i]) ){
							temp = "";
							temp += s.top();
							result.push_back(temp);
							s.pop();
						}
						s.push(str[i]);
					}
				}
			}
		} 
	} 
	while( !s.empty() ){
		temp = "";
		temp += s.top();
		result.push_back(temp);
		s.pop();
	}
	return result; 
}
int Calculate(vector<string> res)
{
	stack<int> result;
	for(int i=0; i<res.size(); i++){
		if( isdigit(res[i][0]) ){ //是操作数 
			result.push(atoi(res[i].c_str())); 
		}else{
			int B = result.top();
			result.pop();
			int A = result.top();
			result.pop();
			
			if( res[i]=="+" ){
				result.push(A+B);
			}
			if( res[i]=="-" ){
				result.push(A-B);
			}
			if( res[i]=="*" ){
				result.push(A*B);
			}
			if( res[i]=="/" ){
				result.push(A/B);
			}
		}
	}
	return result.top();
}