表达式的值

对于1 位二进制变量定义两种运算：

运算的优先级是：

先计算括号内的，再计算括号外的。
“× ”运算优先于“⊕”运算，即计算表达式时，先计算× 运算，再计算⊕运算。例如：计算表达式A⊕B × C时，先计算 B × C，其结果再与 A 做⊕运算。

现给定一个未完成的表达式，例如_+(_*_)，请你在横线处填入数字

输入输出格式

输入格式：

共 2 行。

第1 行为一个整数

第2 行为一个字符串包含

输出格式：

共1 行。包含一个整数，即所有的方案数。注意：这个数可能会很大，请输出方案数对

栈先进后出的数据结构。在该程序中建有两个栈：一个用于存储运算符，还有一个用于存储操作数或运算结果。基本

过程是：

（1）：首先设置操作数栈为空栈，设置运算符栈以‘#’为栈底元素（其优先级最低）。

（2）：通过为栈内栈外运算符设置值而比較其优先级

（3）：依次去找到表达式中的全部运算符和操作数，对于操作数直接入栈。运算符则和运算符栈的

栈顶运算进行比較优先级，若栈内优先级大，则进行对应操作并操作数和栈内运算符都出栈，若优先级相等仅仅需

栈内运算符出栈继续查找下一个运算符就可以，若栈内优先级低则栈外运算符入栈。依次循环知道分析完表达式中

的全部运算符和操作数就可以。

（4）：最后在操作数栈中将仅仅会剩下唯一的一个元素，而该元素也将就会是所求表达式的值。

from: 她叫徐晓jie

由于中缀表示中有操作符的优先级问题，还有可加括号改变运算顺序的问题，所以对于编译程序来说，一般不使用中缀处理表达式。

下面讨论用后缀表达式求解表达式的值：

例：计算中缀表达式A+B*(C-D)-E/F对应的后缀表达式ABCD-*+EF/-，它的计算需要以下12步：

from: watsy

首先把中缀式转换为后缀式。

转换过程

1）若读入的是操作数，入到输出栈

2）读入的是闭括号，把操作栈中的运算符依次出栈，推入输出栈，一直遇到对应开括号为止，把开括号出栈

3）读入的开括号，进运算符栈

4）读入的是运算符，如果运算符栈优先级高，堆栈运算符出栈，出栈操作一直要进行到栈顶运算符优先级低为止，然后把新的运算符入栈

5）在读入操作符结束扣，把运算符栈中所有剩余运算符依次出栈，放入输出栈

6）计算输出堆表达式的

 1 #include<stdio.h>
 2 #include<iostream>
 3 #include<cstdio>
 4 using namespace std;
 5 const int M=10007,N=100005;
 6 int n,i,u[N],v[N],top,k;
 7 char c[N],sta[N],ans[2*N];
 8 int main()
 9 {
10     freopen("a.in","r",stdin);
11     freopen("a.out","w",stdout);
12     cin>>n;
13     for(int i=1;i<=n;i++) cin>>c[i];
14     ans[++k]='.';
15     for(i=1;i<=n;i++)
16     {
17         if(c[i]=='('||c[i]=='*')
18             sta[++top]=c[i];
19         if(c[i]=='+')
20         {
21             while(sta[top]=='*')
22                 ans[++k]=sta[top--];
23             sta[++top]=c[i];
24         }
25         if(c[i]==')')
26         {
27             while(sta[top]!='(')
28                 ans[++k]=sta[top--];
29             top--;
30         }
31         if(c[i]!='('&&c[i]!=')')
32             ans[++k]='.';
33     }
34     while(top>0)
35         ans[++k]=sta[top--];
36     for(i=1;i<=k;i++)
37     {
38         if(ans[i]=='.')
39         {
40             u[++top]=1;
41             v[top]=1;
42         }
43         if(ans[i]=='*')
44         {
45             top--;
46             u[top]=(u[top+1]*v[top]+u[top]*v[top+1]+u[top]*u[top+1])%M;
47             v[top]=v[top]*v[top+1]%M;//注意顺序，放前面u[ftp]先更新，但后面还要用原来的  
48         }
49         if(ans[i]=='+')
50         {
51             top--;
52             v[top]=(u[top+1]*v[top]+u[top]*v[top+1]+v[top]*v[top+1])%M;
53             u[top]=u[top]*u[top+1]%M;
54         }
55     }
56     printf("%d",u[1]);
57 }