思考

表达式求值，其实是一件很简单的事，但是一大段字符串没有空格意味着你要解决逐字输入，这道题很简单，我们只需要把‘*’的先解决，再把‘+’解决了就好..

原题题解

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
using namespace std;
int main()
{
    long long shu,sum=0,cj,sg;
    char ch=0,xg;
    bool tf=true;
    while(tf)
    {
        scanf("%lld",&shu);
        tf=scanf("%c",&xg)==1?true:false;
        if(ch==0)cj=shu;
        if(ch=='+')sum=(sum+cj)%10000,cj=shu;
        if(ch=='*')cj=(cj*shu)%10000;
        if(!tf)sum=(sum+cj)%10000;
        ch=xg;
    }
    printf("%lld",sum);//输出
    return 0;
}

</details>

但是，不能止步于此啊啊啊，表达式求值，不仅仅要有‘*’和‘+’更要有‘-’和‘^’

拥有多个运算符和优先级，首当其冲的应该是有栈啊，处理优先级不会混乱

其次既然有栈了，那么就直接上‘(’和‘)’吧，可以处理的东西也多了

#include <iostream>
#include <stack>
#include <string>
#define MOD 10000
using namespace std;

long long fastPower(long long base, long long power)
{
    long long result = 1;
    while (power > 0)
    {
        if (power & 1)
        {
            result = result * base;
        }
        power >>= 1;
        base = base * base;
    }
    return result;
}

int priority(char a)
{
    if (a == '+' || a == '-')
        return 1;
    if (a == '*' || a == '/')
        return 2;
    if (a == '^')
        return 3;
    if (a == '(')
        return 0;
    return 0;
}

string mid2back(string s) //中缀计算表达式转后缀计算表达式
{
    string res;
    stack<char> st;
    long long size = s.size();
    bool flag = 0;
    for (long long i = 0; i < size; i++)
    {
        if (s[i] >= '0' && s[i] <= '9')
        {
            res += s[i];
            flag = 1;
        }
        else
        {
            if (flag)
            {
                res += ' ';
                flag = false;
            }
            if (s[i] == '(')
                st.push(s[i]);
            if (s[i] != '(' && s[i] != ')')
            {
                if (st.empty())
                    st.push(s[i]);
                else
                    while (1)
                    {
                        char temp = st.top();
                        if (priority(s[i]) > priority(temp)) //栈顶算术符号优先级高于当前算术符号
                        {
                            st.push(s[i]);
                            break;
                        }
                        else
                        {
                            res += temp;
                            res += ' ';
                            st.pop();
                            if (st.empty()) //如果栈空 那么当前算术符号入栈
                            {
                                st.push(s[i]);
                                break;
                            }
                        }
                    }
            }
            if (s[i] == ')')
            {
                while (st.top() != '(')
                {
                    res += st.top();
                    res += ' ';
                    st.pop();
                }
                st.pop();
            }
        }
    }
    while (!st.empty()) //栈中剩余算术符号放入算术表达式
    {
        res += ' ';
        res += st.top();
        st.pop();
    }
    return res; //转换后的算术表达式
}

long long compute(string str) //根据后缀算术表达式计算值
{
    stack<long long> st;
    long long size = str.size();
    bool flag = 0;
    long long temp = 0;
    for (long long i = 0; i < size; i++)
    {
        if (str[i] >= '0' && str[i] <= '9')
        {
            temp = temp * 10 + str[i] - '0';
            flag = 1;
        }
        if (str[i] == ' ' || (str[i] >= '0' && str[i] <= '9' && flag && i == size - 1))
        {
            if (flag)
                st.push(temp);
            flag = 0;
            temp = 0;
        }
        if (str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/' || str[i] == '^')
        {
            long long x = st.top();
            st.pop();
            long long y = st.top();
            st.pop();
            if (str[i] == '*')
                st.push(y * x);
            if (str[i] == '/')
                st.push(y / x);
            if (str[i] == '+')
                st.push(y + x);
            if (str[i] == '-')
                st.push(y - x);
            if (str[i] == '^')
                st.push(fastPower(y, x));
        }
    }
    return st.top(); //返回后缀表达式的计算结果
}
int main()
{
    string str;
    cin >> str;
    cout << compute(mid2back(str)) ;
    return 0;
}

相比之下，这道\color{orange}{普及-}的题还是有点水的啊,对其的扩充和举一反三值得深思（