栈.md

#表达式求值

背景是从键盘录入一个带加减乘除括号的表达式，求出他的值。

首先有以下结论：

• 乘除优先级高于加减。
• 带括号的算式优先级高于不带括号的。

整个表达式可以看做栈模拟与后缀表达式，即对于一个算式：a+b，我们可以先让加号两边的数字入栈，再处理中间的运算符，这就是后缀表达式，记作a b +；一旦遇见括号，先让左括号入栈，遇到右括号时表示带括号的算式已经到头，可以计算，计算完毕之后将新结果入栈，完成更新。

递归以上操作直到表达式录入完毕。

一道经典的表达式求值题目(双栈、比较运算符优先级)--极简代码求解_diadestiny的博客-CSDN博客

# include<bits/stdc++.h>
# include<unordered_map>
using namespace std;
typedef long long ll;
stack<int>num;
stack<char>op;

void val()
{
	int x;
	int b=num.top();num.pop();
	int a=num.top();num.pop();
	
	if(op.top()=='+')
		x=a+b;
		else if(op.top()=='-')
		x=a-b;
		else if(op.top()=='*')
		x=a*b;
		else if(op.top()=='/')
		x=a/b;
	
	op.pop();
	
	num.push(x);
	
	
}
int main (void)
{
	string str;
	cin>>str;
	unordered_map<char,int>pr{{'+',1},{'-',1},{'*',2},{'/',2}};   //散列表，赋给不同运算符优先级
	
	for(int i=0;i<str.size();i++)
	{
		auto c=str[i];
		if(isdigit(c))           //如果表达式中这一项是数字，计算数值并入栈
		{
			int x=0;int j=i;
			while(j<str.size()&&isdigit(str[j]))
			x=x*10+str[j++]-'0';
			
			i=j-1;
			num.push(x);
		}
		else if(c=='(')         //左括号不用理会，直接存入
		op.push(c);
		else if(c==')')         //右括号则计算好所有到左括号之前的数值
		{
			while(op.top()!='(')
			{
				val();
			}
			op.pop();
		}
			else              //如果是四则运算符，入栈并计算已有数值
		{
			while(op.size()&&op.top()!='('&&pr[op.top()]>=pr[c])
			val();
			op.push(c);
			
		}
	}
	while(op.size())        //清理干净op中剩余的运算符
	val();
	
	cout<<num.top()<<endl;
		
	return 0;	
}