栈-表达式求值 NOIP2013 P2

【NOIP2013普及组P2】表达式求值

Time Limit:10000MS Memory Limit:128000K
Total Submit:37 Accepted:19
Case Time Limit:1000MS

Description

给定一个只包含加法和乘法的算术表达式，请你编程计算表达式的值。

Input

输入仅有一行，为需要你计算的表达式，表达式中只包含数字、加法运算符“+”和乘法运算符“*”，且没有括号.
所有参与运算的数字均为0到2^31-1之间的整数。输入数据保证这一行只有0~9、+、*这12种字符。

Output

输出只有一行，包含一个整数，表示这个表达式的值。注意：当答案长度多于4位时，请只输出最后4位，前导0不输出。

Sample Input

【样例1】
1+1*3+4
【样例2】
1+1234567890*1
【样例3】
1+1000000003*1

Sample Output

【样例1】
8
【样例2】
7891
【样例3】
4

Hint

【样例说明】
样例1计算的结果为8，直接输出8。
样例2计算的结果为1234567891，输出后4位，即7891。
样例3计算的结果为1000000004，输出后4位，即4。

【数据范围】
对于30%的数据，0≤表达式中加法运算符和乘法运算符的总数≤100；
对于80%的数据，0≤表达式中加法运算符和乘法运算符的总数≤1000；
对于100%的数据，0≤表达式中加法运算符和乘法运算符的总数≤100000。

Source

中缀表达式求值——用两个栈 sign[] 和 num[] 分别存储符号和数字。

当读入的字符是数字的时候：

用 tt 表示当前读到的单个数字，则 number = number * 10 + tt

当读入的字符是符号的时候：

1.此时可以保证之前读入的一个完整数字 number 已经可以放入 num 栈当中了，即 num[++topn] =number ；并将 number 赋值为 0 ，便于下次正确读入一个完整数字；

a.)如果当前读到的运算符优先级低于或等于前一个（即 sign 栈顶）运算符优先级，则前面读到的两个数（num[topn - 1] 和 num[topn]）可以进行运算，并把运算后的结果直接替代到 num[topn - 1] ——举个例子，对于这个式子 3 * 2 + 1 ，当读入到加号的时候便可以把式子从 3 * 2 + 变化为 6 + 了；

b.)如果当前读入的运算符优先级大于之前读入的运算符，则正常压入符号栈 sign 当中；

请注意，当我们这样完整地一边读入一边处理完一个式子之后，此时的简化后的式子一定满足：前面的运算符优先级小于等于后面（即运算符升序排列）——这是因为如果读入时一个式子优先级大于等于后面的运算符，则已经被提前计算并化简成一个数字，比如 3 * 2 + 1 ，在读入加号时便把 3 * 2 化为 6 了。

既然此时的式子满足这样一个顺序（运算符升序排列），我们只要从后往前把式子算一遍就可以得出表达式的值了。

写到这里，程序框架已经很清晰了；当然，针对于题目而言自然有一些相应的细节。比如，这道题当中只要求输出最后 4 位，所以运算过程当中是可以随时取模 10000（=10^4）的（实际上也需要这么做，因为尽管每个数不会超过 2^31 - 1 ，但它们的积或和就不一定了，是很有可能爆 long long int 的）。

附上一份代码。

 1 #include <cstdio>
 2 long long int num[100005];
 3 char sign[100005], temp[4];
 4 int lv[100005], signlv[260];
 5 int topn, tops;
 6 long long int number;
 7 
 8 long long int f(char s)
 9 {
10     switch (s) {
11     case '+':
12         return (num[topn] + num[topn + 1]) % 10000;
13     case '*':
14         return (num[topn] * num[topn + 1]) % 10000;
15     default:
16         return -1;
17     }
18     return -1;
19 }
20 
21 void init()
22 {
23     lv[0] = -1;
24     signlv['+'] = 1;
25     signlv['*'] = 2;
26     return ;
27 }
28 
29 void solve()
30 {
31     char tt;
32     while ((tt = getchar()) != '
') {
33         switch (tt) {
34         case '+':
35         case '*': {
36             num[++topn] = number;
37             number = 0;
38             if (lv[tops] < signlv[tt])
39                 ++tops;
40             else
41                 num[--topn] = f(sign[tops]);
42             sign[tops] = tt;
43             lv[tops] = signlv[tt];
44             break;
45         }
46         default: {
47             number = number * 10 + tt - '0';
48             break;
49         }
50         }
51     }
52     num[++topn]= number;
53     while (tops)
54         num[--topn] = f(sign[tops--]);
55     return ;
56 }
57 
58 void output()
59 {
60     bool flag = false;
61     temp[0] = num[1] % 10;
62     temp[1] = (num[1] /= 10) % 10;
63     temp[2] = (num[1] /= 10) % 10;
64     temp[3] = (num[1] /= 10) % 10;
65     if (!temp[0] && !temp[1] && !temp[2] && !temp[3]) {
66         putchar('0');
67         putchar('
');
68         return ;
69     }
70     if (temp[3] || flag) {
71         putchar(temp[3] + '0');
72         flag = true;
73     }
74     if (temp[2] || flag) {
75         putchar(temp[2] + '0');
76         flag = true;
77     }
78     if (temp[1] || flag) {
79         putchar(temp[1] + '0');
80         flag = true;
81     }
82     if (temp[0] || flag)
83         putchar(temp[0] + '0');
84     putchar('
');
85     return ;
86 }
87 
88 int main()
89 {
90     init();
91     solve();
92     output();
93     return 0;
94 }

ghcred's Code