题解 | #表达式求值#

/*HJ54表达式求值
给定一个字符串描述的算术表达式，计算出结果值。
输入字符串长度不超过 100 ，合法的字符包括 ”+, -, *,
 /, (, )” ， ”0-9” 。
能通过测试用例，但是不能算‘-’后面是‘（’的情况，比如‘-（1+2）’
听起来简单编起来真的好累！！！！！！！！
*/
#include <iostream>
#include <stack>
using namespace std;
int priority(char a)
{
	switch(a)
	{
		case '(' :
			return 1;break;
		case ')' :
			return 1;break;			
		case '+':
			return 2;break;
		case '-':
			return 2;break;
		case '*':
			return 3;break;
		case '/':
			return 3;break;
		default:return -1;break;
	}
}
int operate(int a,int b,char x)
{
	int result;
	switch(x)
	{
		case '+':
			result=a+b;
			break;
		case '-':
			result=a-b;
			break;
		case '*':
			result=a*b;
			break;
		case '/':
			result=a/b;
			break;
		default:
			break;		
	}
	return result;	
}
int main()
{
	string a;
	int t=0;//字符串转操作数 
	int p=0,q=0;//操作数寄存 
	int num;//最终数字 
	int opnd1[200];
	char optr1[200];
	int r=0,s=0;
	getline(cin,a);
	stack<int> opnd;//操作数栈 
	stack<char> optr;//运算符栈 
	for(int i=0;i<a.length();i++)
	{
		if(a[i]>='0'&&a[i]<='9')//字符转操作数 
		{
			if(a[i-1]>='0'&&a[i-1]<='9')//前一个数也是数字 
			{
				t=opnd.top()*10+a[i]-'0';//匹配数字，重新压栈 
				opnd.pop();
				opnd.push(t);
			}			 
			else opnd.push(a[i]-'0');
		}
		else if(a[i]=='+'||a[i]=='-'||a[i]=='*'||a[i]=='/'||a[i]=='('||a[i]==')')
		{
			if(((opnd.empty()&&optr.empty())&&a[i]=='-'||(a[i-1]=='('&&a[i]=='-'))&&(a[i+1]>='0'&&a[i+1]<='9'))
			{
				t=-(a[i+1]-'0');
				opnd.push(t);
				i++;				
				continue;
			}				
			else if(optr.empty()||a[i]=='(')
			{
				optr.push(a[i]);
				continue;
			}					
			else if(priority(a[i])>priority(optr.top()))
				optr.push(a[i]);
			else 
			{
				while(priority(a[i])<=priority(optr.top()))
				{
					if(a[i]==')'&&optr.top()=='(') 
					{
						optr.pop();
						break;
					}
					p=opnd.top();
					opnd.pop();
					q=opnd.top();
					opnd.pop();//出栈两个元素 
					opnd.push(operate(q,p,optr.top()));
					optr.pop(); 
					if(optr.empty()) break;				
				}
				if(a[i]!=')') optr.push(a[i]);
			}							
		}
	}
	while(!optr.empty())
	{
		p=opnd.top();
		opnd.pop();
		q=opnd.top();
		opnd.pop();//出栈两个元素 
		opnd.push(operate(q,p,optr.top()));
		optr.pop(); 
	}
	while(!opnd.empty())
	{
		opnd1[r]=opnd.top();
		opnd.pop();//出栈元素 
		r++;
	}
	while(!optr.empty())
	{
		optr1[s]=optr.top();
		optr.pop();
		s++;
	}
//	int j=s-1;
//	for(int i=r-1;i>=0;i--)
//	{
//		if(i==r-1)
//		{
//			num=operate(opnd1[i],opnd1[i-1],optr1[j]);
//			i--;
//		}		
//		else 
//		{
//			num=operate(num,opnd1[i],optr1[j]);
//		}
//		j--;
//	}	
//	cout<<num<<endl;
	for(int i=r-1;i>=0;i--)
	{
		cout<<opnd1[i]<<" ";
	}
	for(int i=s-1;i>=0;i--)
	{
		cout<<optr1[i]<<" ";
	}
}