输入一个含括号的加减乘除表达式，输出该表达式的值：

 

思路：输入表达式，注意(可能带有括号)，运用两个栈，符号栈和数字栈，首先判断优先级，把所有符号的优先级打表，进行运算，入栈时模仿单调栈，如果当前 优先级比栈顶元素优先级小，说明当前元素需要赶快计算，不然会影响以后的结果。例如2*3-2，‘-’进来的时候，优先级比’*’小，所以先把*运算运行完，运行完之后再把减号放进来。如果遇到优先级相等的情况即()的情况，就把现在括号内的都清空。另外我们可以在 字符串 前面后面都加一个#，防止最后计算不完的情况。

解释一下为什么 ，新来的优先级要比栈顶元素的优先级高

看一下这个例子:

2*3+1  当来到'+'时，这时候加号的优先级比栈顶元素'*'底，说明前面的计算必须要完成了，要不然会出错。

然后注意括号 栈顶元素 括号 的优先级 要比 新来括号的优先级低，要让他入栈。

AC：

#include<bits/stdc++.h>
const int maxn=1000250;
using namespace std;
typedef long long ll;
struct num{
	int *base;
	int size,len;
	void inint()
	{
		size=maxn;
		base=(int*)malloc(sizeof(int)*maxn);
		len=0;
	}
	int empty()
	{
		if(!len) return 1;
		return 0;
	}
	void push(int x)
	{
		base[++len]=x;
	}
	void pop()
	{
		len--;
	}
	int top()
	{
		return base[len];
	}
}st;
struct oper{
	char *base;
	int size,len;
	void inint()
	{
		size=maxn;
		base=(char*)malloc(sizeof(char)*maxn);
		len=0;
	}
	int empty()
	{
		if(!len) return 1;
		return 0;
	}
	void push(char x)
	{
		base[++len]=x;
	}
	void pop()
	{
		len--;
	}
	char top()
	{
		return base[len];
	}
}op;
char str[maxn];
int p[10][10]={
{0},
{0,1,1,0,0,0,1,1},
{0,1,1,0,0,0,1,1},
{0,1,1,1,1,0,1,1},
{0,1,1,1,1,0,1,1},
{0,0,0,0,0,0,2,-1},
{0,1,1,1,1,-1,1,1},
{0,0,0,0,0,0,-1,2}
};
int Creatmap(char a)
{
	switch(a)
	{
		case '+':return 1;
		case '-':return 2;
		case '*':return 3;
		case '/':return 4;
		case '(':return 5;
		case ')':return 6;
		case '#':return 7;
	}
}
int Cmp(char a,char b)// a是栈顶元素
{
	return p[Creatmap(a)][Creatmap(b)];
}
int cal(int a,int b,char ch)
{
	switch(ch)
	{
		case '+':return a+b;
		case '-':return a-b;
		case '*':return a*b;
		case '/':return a/b;
	}
}
void solve()
{
	int len=strlen(str);
	for(int i=0;i<len;i++)
	{
	    if(str[i]==' ') continue;
		if(str[i]>='0'&&str[i]<='9')
		{
			int x=0;
			while(str[i]>='0'&&str[i]<='9')
			{
				int temp=str[i]-'0';
				x=x*10+temp;
				i++;
			}
			i--;//不满足的时候多加了1
			st.push(x);
		}
		else
        {
            if(op.empty()||!Cmp(op.top(),str[i]))
                op.push(str[i]);
            else if(Cmp(op.top(),str[i])>0)
            {
                while(!op.empty()&&Cmp(op.top(),str[i])>0)
                {
                    if(Cmp(op.top(),str[i])==2)
                    {
                        op.pop();
                        break;
                    }
                    else if(Cmp(op.top(),str[i])==1)
                    {
                        int x=st.top();st.pop();
                        int y=st.top();st.pop();
                        int z=cal(y,x,op.top());
                        st.push(z);
                        op.pop();
                    }
                }
                if(str[i]!='#'&&str[i]!=')') op.push(str[i]);
            }
        }
	}
	printf("%d\n",st.top());
}
int main()
{
	st.inint();r
	op.inint();
	scanf("%s",str+1);
	int len=strlen(str+1);
	str[0]='#';str[len+1]='#';
	str[len+2]='\0';
	solve();
}
/***
7-6*(2/1+2)
***/

运行结果：

优先级表参照：《数据结构》 宋丽华 张小峰老师著