表达式求值

表达式

简单的表达式只包含操作数、+、-、*、/、（、）。根据运算符与操作数的位置关系，可分为前缀表达式、中缀表达式、后缀表达式。

我们日常的算术运算用的就是中缀表达式，对中缀表达式的求值过程就是先将中缀表达式转换成后缀表达式，然后对该后缀表达式求值。(其实这两个步骤不必显式的表现出来，可以合二为一)

思路

归纳一：在扫描exp遇到一个运算符op时，如果栈为空，直接将其进栈；如果不为空，只有当op的优先级高于栈顶运算符的优先级才直接将op进栈；否则依次出栈运算符(同时取mp中的元素进行运算)，直到栈顶为空或者栈顶运算符的优先级小于op的优先级为止，然后再将op进栈

归纳二：在扫描exp遇到一个，如果op为‘（’，表示一个子表达式的开始，直接将其进栈；如果op为’）‘，表示一个子表达式的结束，将栈顶元素不断出栈(同时去mp中的元素进行运算)，知道遇到’（‘；如果是其它运算符，而栈顶为'(',直接将其进栈。

 1 void solve()
 2 {
 3     stack<double>mp;     //存操作数
 4     stack<char>op;         //存运算符
 5     遍历整个表达式
 6     {
 7         char ch = expn[i];
 8         
 9         if (ch是数字)
10         {
11             获得完整的数字;
12             将其入栈mp;
13         }
14         else
15         {
16             if (ch是左括号)  将其入栈op
17             else if (ch是右括号)
18             {
19                 while (op.top()不为左括号)
20                     cal_num(mp, op);
21                 op.pop();     //为了消去'('
22             }
23             else if (栈为空 或 当前运算符优先级大于栈顶元素)  直接入栈;
24             else
25             {
26                 while (栈非空 且 当前运算符优先级小于或等于栈顶元素)
27                     cal_num(mp, op);
28                 op.push(ch);   //记得把当前运算符入栈
29             }
30         }
31     }
32     op.pop();    //清空栈
33     输出mp栈顶元素(即表达式的值);34     mp.pop();    //清空栈
35 }

例题

随便输入一个表达式，表达式里只包含+-*/与小括号这几种符号(不含空格)。其中小括号可以嵌套使用。数据保证输入的操作数中不会出现负数。数据保证除数不会为0。

原题链接：http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=35

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<stack>
 4 #include<cstring>
 5 #include<iostream>
 6 using namespace std;
 7 
 8 const int maxn = 1000 + 10;
 9 char expn[maxn];
10 
11 int cal_priority(char ch)
12 {
13     if (ch == '(' || ch == '=')  return 0;   //定义为优先级最低，这样只有遇到左括号才会出栈
14     if (ch == '+' || ch == '-')  return 1;
15     if (ch == '*' || ch == '/')   return 2;
16     if (ch == ')')  return 3;
17 
18 }
19 
20 void cal_num(stack<double> &mp,stack<char> &op)
21 {
22     double a = mp.top(); mp.pop();
23     double b = mp.top(); mp.pop();
24     char c = op.top(); op.pop();
25     switch (c)
26     {
27         case '+':mp.push(b + a); break;
28         case '-':mp.push(b - a); break;
29         case '*':mp.push(b * a); break;
30         case '/':mp.push(b / a); break;
31     }
32 }
33 
34 void solve()
35 {
36     stack<double>mp;
37     stack<char>op;
38     int len = strlen(expn);
39     for (int i = 0; i < len; i++)
40     {
41         char ch = expn[i];
42         
43         if (isdigit(ch))
44         {
45             double num = atof(&expn[i]);   //传入首地址，自动转换为对应的数字
46             while (i < len && (isdigit(expn[i])||expn[i] == '.'))
47                 i++;
48             i--;
49             mp.push(num);
50         }
51         else
52         {
53             if (ch == '(')  op.push(ch);
54             else if (ch == ')')
55             {
56                 while (op.top() != '(')
57                     cal_num(mp, op);
58                 op.pop();     //为了消去'('
59             }
60             else if (op.empty() || cal_priority(ch) > cal_priority(op.top()))  op.push(ch);
61             else
62             {
63                 while (!op.empty() && cal_priority(ch) <= cal_priority(op.top()))
64                     cal_num(mp, op);
65                 op.push(ch);
66             }
67         }
68     }
69     op.pop();    //清空栈
70     printf("%.2lf
", mp.top());
71     mp.pop();    //清空栈
72 }
73 
74 int main()
75 {
76     int T;
77     scanf("%d", &T);
78     while (T--)
79     {
80         scanf("%s", expn);
81         solve();
82     }
83     return 0;
84 }

参考链接：http://acm.nyist.edu.cn/JudgeOnline/bestcode.php?pid=35