学步园

题目描述

    模拟计算机处理算术表达式过程，从键盘上输入算术表达式串，表达式只包括'+','-','*','/'四种运算符，数字和括号，其中'-'只表示减号，不表示负数，即表达式里不存在负数，'/'如果不能整除，结果只取商，保证输入的字符串是合法的，求出该表达式的值

输入格式

只有一行为一个表达式，长度小于100

输出

只有一行，为表达式的值

样例输入

(123+321)*(2-3)/5

样例输出

-88

【分析】

此题基本上是在中缀转后缀的基础上进行了结果的计算，可以先把表达式用中缀转后缀的方法，用两个栈来存储，一个栈存储数，另外一个栈存储运算符，转换完了，再对运算符栈逐一出栈，出一个运算符，就把数值所在的栈的栈顶的两元素进行运算结果存在栈顶(栈顶两元素，一个出栈，另一个更新成运算后的结果)。
我没有转完后再计算，而是边转变计算，其实转完后再计算细节更好处理，根据自己的习惯看着办

#include<iostream>
#include<stack>
#include<cstring>
#include<cstdio>
using namespace std;
string s;
stack<int> number;
stack<char> symbol;
int get_pre(char,bool);
bool is_operator(char);
void my_calc();
void work();
int main()
{
	cin>>s;
	work();
	return 0;
}
bool is_operator(char ch)
{
	if(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch==')'||ch=='(')return true;
	else return false;
}
int get_pre(char ch,bool flag)
{
	if(ch=='+'||ch=='-')return 1;
	if(ch=='/'||ch=='*')return 2;
	if(ch=='('&&flag)return 0;
	if(ch=='('&&!flag)return 3;
	return 4;
}
void my_calc()//当运算符出栈时，计算结果 
{
	int y=number.top();//取出存储数值栈的栈顶元素 
	number.pop();//栈顶元素出栈，下面把更新过的结果放在当前栈顶中 
	if(symbol.top()=='+') number.top()+=y;
	if(symbol.top()=='-') number.top()-=y;
	if(symbol.top()=='*') number.top()*=y;
	if(symbol.top()=='/') number.top()/=y;				
	symbol.pop();//运算符出栈 
}
void work()
{
	int i=0;
	while(i<s.size())//枚举表达式 
	{
		if(!is_operator(s[i]))//如果是数 
		{
			int x=0;//数不一定是一位的，如果是多位，通过while逐一取出 
			while(i<s.size()&&!is_operator(s[i]))
			{				
				x=x*10+s[i]-48;
				i++;
			}		
			number.push(x);	//把转换的数压入数栈中 
			continue;	
		}
		
		if(s[i]=='(')
		{
			symbol.push(s[i]);
			i++;//这个容易忽略，不然有可能死循环 
			continue;
		} 
		if(s[i]==')')
		{
			while(symbol.top()!='(')//把'('之前的所有运算符弹出，并计算 
			{
				my_calc();
			}
			symbol.pop();//把'('出栈 
			++i;
			continue;
		}
		while(!symbol.empty()&&get_pre(s[i],false)<=get_pre(symbol.top(),true))
		{
			my_calc();//当当前字符优先级不高于运算符栈栈顶元素，出栈并计算 
		}
		symbol.push(s[i]);//当前字符进栈 
		i++;
	}	
	while(!symbol.empty())
	{
		my_calc();
	}
	cout<<number.top()<<endl;
}