[https://www.luogu.com.cn/problem/P1310]([NOIP2011 普及组] 表达式的值)

神仙题， 被吊着打qaq

这不就是一个求表达式树的后序遍历吗. \(—zwd\)

水题。 水题。 虐了我两次。 qaq

然后就开始了表达式的恶补

首先是把表达式转成后缀表达式 因为好求

---

转的方法：

1. 如果有数字 直接放在后缀表达式中

2. 如果是运算符 把运算符低于他的运算符加入表达式中， 并出栈， 再把这个运算符放入栈

3. 有括号的情况就是把括号里的全部放进去

---

怎么求

我们可以按顺序扫描整个字符串， 发现一个数字就放入数字栈， 发现一个运算符取出数字栈栈顶的两个数， 进行运算， 压入数字栈

---

我们这道题是要自己补数字， dp数组记的是第i个位置0有多少种可能1有多少种可能， 按表达式求值算就行了

#include <bits/stdc++.h>
using namespace std;
#define Mod 10007
#define int long long
const int N= 200005;
char stk[N], ans[N], num[N];
int top, tot, cnt;
int dp[N][2];

signed main()
{
	int n; cin>> n;
	string s; cin>> s;
	ans[++ tot]= '_';
	for(int i=0; i<s.size(); i++)
	{
		if(s[i]== '*'|| s[i]== '(') stk[++ top]= s[i];
		else if(s[i]== '+')
		{
			while(stk[top]== '*') ans[++ tot]= stk[top-- ];
			stk[++ top]= s[i];
		} 
		else if(s[i]== ')')
		{
			while(stk[top]!= '(') ans[++ tot]= stk[top-- ];
			top-- ;
		}
		if(s[i]!= '('&& s[i]!= ')') ans[++ tot]= '_';
	}
	while(top) ans[++ tot]= stk[top-- ];
	
	for(int i=1; i<=tot; i++)
	{
		if(ans[i]== '_')
		{
			dp[++ cnt][0]= 1; dp[cnt][1]= 1;        //不能连等！！！！
			continue;
		}
		if(ans[i]== '*')
		{
			dp[cnt- 1][0]= dp[cnt- 1][0]* (dp[cnt][0]+ dp[cnt][1])% Mod+ dp[cnt- 1][1]* dp[cnt][0]% Mod;
			dp[cnt- 1][1]= dp[cnt- 1][1]* dp[cnt][1]% Mod;
		}
		else
		{
		    dp[cnt- 1][1]= dp[cnt- 1][1]* (dp[cnt][0]+ dp[cnt][1])% Mod+ dp[cnt- 1][0]* dp[cnt][1]% Mod;
			dp[cnt- 1][0]= dp[cnt- 1][0]* dp[cnt][0]% Mod;
		}
		cnt-- ;
	} 
	cout<< dp[1][0]% Mod<< endl;
	return 0;
}
/*
5
***+*
*/