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

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

题目背景

NOIP2013 普及组 T2

题目描述

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

输入格式

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

输入数据保证这一行只有 0123456789+* 这 $12$ 种字符。

输出格式

一个整数，表示这个表达式的值。

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

样例 #1

样例输入 #1

1+1*3+4

样例输出 #1

8

样例 #2

样例输入 #2

1+1234567890*1

样例输出 #2

7891

样例 #3

样例输入 #3

1+1000000003*1

样例输出 #3

4

提示

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

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

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

解题

思想

总体需要注意两点：

1. 注意只输出后4位
2. 注意连乘的情况！！！

代码

#include <bits/stdc++.h>
using namespace std;

stack<int> st;
stack<int> result;
int a, b, c=0;
string _str;

bool isPriority(char op){
    return op == '+' || op == '*';
}

int getNum(stack<int> st){
    int ans=0;
    int j=0;
    while (!st.empty() && j<4)
    {
        ans += st.top()*pow(10,j++);
        st.pop();
        ans = ans%10000;
    }
    return ans;
}

int main()
{
    cin >> _str;
    _str.append("+");

    for (int i = 0; i < _str.length(); i++)
    {
        if (_str[i] == '+')
        {
            int k =  getNum(st);
            while (!st.empty())
            {
                st.pop();
            }
            result.push(k);
        } 
        else if (_str[i] == '*')
        {
            if (st.empty())
            {
                a = result.top();
                result.pop();
            }
            else
            {
                a = getNum(st);
                while (!st.empty())
                {
                    st.pop();
                }
            }
            i++;
            while (i < _str.length())
            {
                if (isPriority(_str[i]))
                {
                    i--;
                    break;
                }
                else
                {
                    st.push(int(_str[i++]-'0'));
                }
            }
            b = getNum(st);
            while (!st.empty())
            {
                st.pop();
            }
            result.push((a*b)%10000);
        }
        else
        {
            st.push(int(_str[i]-'0'));
        }
    }
    
    while (!result.empty())
    {
        c+=result.top();
        result.pop();
        c=c%10000;
    }
    cout << c;

    return 0;
}

踩坑

关于字符和数字混合输入

• 可以全当做字符串处理
• 也可以像下面这样
  
  

参考资料

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