P1981 [NOIP2013 普及组] 表达式求值

落日映苍穹つ 2023-01-13 09:34 280阅读 0赞

## [P1981 \[NOIP2013 普及组\] 表达式求值][P1981 _NOIP2013 _] ##

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

**输入格式**  
一行，为需要你计算的表达式，表达式中只包含数字、加法运算符“ \+ + \+”和乘法运算符“ × \\times ×”，且没有括号，所有参与运算的数字均为  0 0 0 到  2 31 − 1 2^\{31\}-1 231−1之间的整数。

输入数据保证这一行只有 0 − 9 0-9 0−9、 \+ + \+、 × \\times ×这 1212种字符。

**输出格式**  
一个整数，表示这个表达式的值。

注意：当答案长度多于 4 位时，请只输出最后4 位，前导 0 不输出。

**输入输出样例**  
**输入1**

1+1*3+4

**输出1**

**输入2**

1+1234567890*1

**输出2**

7891

**输入3**

1+1000000003*1

**输出3**

**说明/提示**  
对于  30 % 30\\% 30%的数据， 0 ≤ 表 达 式 中 加 法 运 算 符 和 乘 法 运 算 符 的 总 数 ≤ 100 0≤表达式中加法运算符和乘法运算符的总数≤100 0≤表达式中加法运算符和乘法运算符的总数≤100；

对于  80 % 80\\% 80%的数据， 0 ≤ 表 达 式 中 加 法 运 算 符 和 乘 法 运 算 符 的 总 数 ≤ 1000 0≤表达式中加法运算符和乘法运算符的总数≤1000 0≤表达式中加法运算符和乘法运算符的总数≤1000；

对于 100 % 100\\% 100%的数据， 0 ≤ 0≤ 0≤表达式中加法运算符和乘法运算符的总数 ≤ 100000 ≤100000 ≤100000。

## 解决问题 ##

既然数字是0~232\-1那么用int是麻烦了，所以每一次需要%m，这样防止溢出，用一个栈模拟即可。先乘后加这个也很好解决，在第一次循环时只处理乘法，第二次再处理加法。

## 代码 ##

这个namespace很是无用，大家可以把它拆出来

#include <stack>
    #include <string>
    #include <cstdio>
    #include <cstring>
    #include <iostream>
    
    using namespace std;
    namespace P1981
    { 
        void play();
        void ZHUANGBI(int s);
        int NOUSE(int s);
    }
    int P1981::NOUSE(int s)
    { 
        return s;
    }
    void P1981::ZHUANGBI(int s)
    { 
        cout << NOUSE(s) << endl;
    }
    void P1981::play()
    { 
        char c = ' ';
        int n = 0, t1, t2, s = 0;
        const int m = 10000;
        cin >> t1;
        stack<int> st;
        st.push(t1);
        while (cin >> c >> t2)
        { 
            if (c == '*')
            { 
                t1 = st.top();
                st.pop();
                st.push(t1 * t2 % m); // %m很重要，因为我们不确定longlong会不会溢出
            }
            else
            { 
                st.push(t2);
            }
        }
        while (!st.empty())
        { 
            s += st.top();
            s %= m; // %m很重要
            st.pop();
        }
        ZHUANGBI(s);
    }
    int main()
    { 
        P1981::play();
        return 0;
    }

[P1981 _NOIP2013 _]: https://www.luogu.com.cn/problem/P1981