中缀表达式求值

步骤:

1.中缀表达式由于有括号和运算优先级很难处理,我们转为后缀表达式

2.后缀表达式求值

一.中缀表达式转后缀表达式过程:

需要开一个栈来处理运算符(只存运算符)

1.如果当前位为数字直接加入后缀表达式中

2.如果为'('同样直接加入后缀表达式中

3.如果为运算符号,那么比较该符号与栈顶运算符的运算优先级:

若大于栈顶,则直接加入栈中

若小于栈顶,则弹出栈顶,并将栈顶元素加入后缀表达式中,直到栈空或大于为止.

4.如果为')'那么直接将弹出直到出现'(',并把弹出元素加入后缀表达式中

二.后缀表达式求值:

这个是基础的东西,也很好写,需要开一个栈存数字

1.遇到数字直接入栈.

2.遇到运算符,则计算栈顶和栈顶的前一个元素在该运算符下的值,并合并两个元素

最后栈顶就是答案

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <cstdio>
 6 #include <cmath>
 7 using namespace std;
 8 const int N=1055,mod=10007,mov=2e5;
 9 char s[N];int n,top=0;char st[N];int t[N];
10 bool comper(char s1,char s2){ // 比较优先级的函数
11     if(s2=='(')return false;
12     if((s2=='+' || s2=='-') && (s1=='*'))return false;
13     return true;
14 }
15 int sum=0;
16 int a[N];
17 void cal(){//后缀表达式求值
18     int top=0;
19     for(int i=1;i<=sum;i++){
20         if(t[i]<=mov){  
21             a[++top]=t[i];
22             continue;
23         }
24         if(t[i]=='+'+mov)a[top-1]+=a[top],top--,a[top]%=mod;
25         else if(t[i]=='-'+mov)a[top-1]-=a[top],top--,a[top]%=mod;
26         else if(t[i]=='*'+mov)a[top-1]*=a[top],top--,a[top]%=mod;
27     }
28     puts("0");
29     printf("%d
",((a[1]%mod)+mod)%mod);
30 }
31 void work(){
32     int k;
33     scanf("%s",s+1);
34     n=strlen(s+1);
35     for(int i=1;i<=n;i++){
36         if(s[i]>='0' && s[i]<='9'){
37             k=s[i]-48;
38             while(s[i+1]>='0' && s[i+1]<='9'){
39                 i++;k=k*10+s[i]-48;
40             }
41             t[++sum]=k;
42             continue;
43         }
44         if(s[i]=='('){
45             st[++top]=s[i];
46             continue;
47         }
48         if(s[i]==')'){
49             while(top && st[top]!='(')
50                 t[++sum]=st[top--]+mov;//mov 为偏移量,为了区分数字和运算符
51             top--;
52             continue;
53         }
54         while(top && comper(s[i],st[top]))
55             t[++sum]=st[top--]+mov;
56         st[++top]=s[i];
57     }
58     while(top)t[++sum]=st[top--]+mov;
59     cal();
60 }
61 int main()
62 {
63     work();
64     return 0;
65 }