题目描述

【题目描述】

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

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

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

【样例输出1】
8

【样例输入2】
1+1234567890*1

【样例输出2】
7891

【样例输入3】
1+1000000003*1

【样例输出3】
4

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

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

思路

建立两个栈，一个存放操作数，一个存放操作符，遇到操作数全部入栈，遇到操作符，判断优先级，如果栈顶操作符的优先级大于当前操作符的优先级，则操作数栈弹出两个操作数，操作符栈弹出一个操作符，进行运算，运算结果放入操作数栈中，如果栈顶操作符的优先级小于当前操作符的优先级，则继续入栈。可以在表达式的前后加上两个‘#’号，在前后两个‘#’号相遇时，循环结束。

代码一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
//
// Created by qyh-mac on 2017/7/29.
//

#include <iostream>
#include <stack>
#include <cctype>
#include <cstdio>

using namespace std;

int main() {
    freopen("expr2013.in", "r", stdin);
    freopen("expr2013.out", "w", stdout);
    string s;
    stack<long long> S;
    stack<char> SS;
    cin >> s;
    int i = 0;
    long long num = 0;
    while(i < s.size()) {
        if(isdigit(s[i])) {
            num = num * 10 + s[i++] - '0';
        }
        else {
            S.push(num);
            num = 0;
            if(SS.empty()) {
                SS.push(s[i++]);
            } else {
                if(SS.top() == '+' && s[i] == '*') {
                    SS.push(s[i++]);
                } else {
                    int a = S.top();
                    S.pop();
                    int b = S.top();
                    S.pop();
                    char op = SS.top();
                    SS.pop();
                    SS.push(s[i++]);
                    long long res = (op == '+') ? (a + b) : (a * b);
                    S.push(res % 10000);
                }
            }
        }
    }
    S.push(num);
    while(!SS.empty()) {
        int a = S.top();
        S.pop();
        int b = S.top();
        S.pop();
        char op = SS.top();
        SS.pop();
        long long res = (op == '+') ? (a + b) : (a * b);
        S.push(res % 10000);
    }

    cout << S.top() % 10000 << endl;
}

代码二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//
// Created by qyh-mac on 2017/7/30.
//

#include <iostream>
#include <stack>
#include <cstdio>
using namespace std;

int main() {
    freopen("expr2013.in", "r", stdin);
    freopen("expr2013.out", "w", stdout);
    string s;
    stack<int> opnd;
    stack<char> optr;
    optr.push('#');
    cin >> s;
    s.append(1, '#');
    int i = 0;
    int num = 0;
    while(i < s.size() || optr.top() != '#') {
        if(isdigit(s[i])) {
            num = num * 10 + s[i++] - '0';
        } else {
            opnd.push(num % 10000);
            num = 0;
            if(optr.size() < 2 || (optr.top() == '+' && s[i] == '*')) {
                optr.push(s[i++]);
            } else {
                int a = opnd.top();
                opnd.pop();
                int b = opnd.top();
                opnd.pop();
                char op = optr.top();
                optr.pop();
                num = (op == '+') ? (a + b) : (a * b);
            }
        }
    }
    cout << opnd.top() << endl;
}