模拟

例题 #1 表达式计算4

题目描述

给出一个表达式，其中运算符仅包含 +，-，*，/，^，要求求出表达式的最终值。

数据可能会出现括号情况，还有可能出现多余括号情况。

数据保证不会出现超过 int 范围的数据，数据可能会出现负数情况。

---

/*                                                                                
                      Keyblinds Guide
                    ###################
      @Ntsc 2024

      - Ctrl+Alt+G then P : Enter luogu problem details
      - Ctrl+Alt+B : Run all cases in CPH
      - ctrl+D : choose this and dump to the next
      - ctrl+Shift+L : choose all like this
      - ctrl+K then ctrl+W: close all
      - Alt+la/ra : move mouse to pre/nxt pos'

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

#define rep(i, l, r) for (int i = l, END##i = r; i <= END##i; ++i)
#define per(i, r, l) for (int i = r, END##i = l; i >= END##i; --i)
#define pb push_back
#define mp make_pair
#define int long long
#define pii pair<int, int>
#define ps second
#define pf first


#define itn int




#define rd read()
int read(){
    int xx = 0, ff = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            ff = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
      xx = xx * 10 + (ch - '0'), ch = getchar();
    return xx * ff;
}
void write(int out) {
    if (out < 0)
        putchar('-'), out = -out;
    if (out > 9)
        write(out / 10);
    putchar(out % 10 + '0');
}

#define ell dbg('\n')
const char el='\n';
const bool enable_dbg = 1;
template <typename T,typename... Args>
void dbg(T s,Args... args) {
    if constexpr (enable_dbg){
    cerr << s;
    if(1)cerr<<' ';
        if constexpr (sizeof...(Args))
            dbg(args...);
    }
}

#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() { cerr << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cerr << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }
#else
#define dbg(...)
#endif


const int N = 3e5 + 5;
const int INF = 1e18;
const int M = 1e7;
const int MOD = 1e9 + 7;


string s="0";
char x;
stack<int>vi;
stack<char>vc;
int T;
int cnt1,cnt2,cnt;

void solve(){


    while(cin>>x){
        if(x==' ')continue;
        s+=(char)x;
    }
    for(int i = 0;i < s.size();i ++){
        char c = s[i];
        if(c=='(')cnt1++;
        if(c==')')cnt2++;
    }
    cnt=max(cnt1,cnt2),cnt++;
    for(int i = 0;i < cnt-cnt1;i ++)
    s='('+s;
    for(int i = 0;i < cnt-cnt2;i ++)
    s=s+')';


    for(int i = 0;i < s.size();i ++){
        char c = s[i];
        int f=1;
        if(c=='-'&&(s[i-1]<'0'||s[i-1]>'9'))
        f = -1;
        if(c>='0'&&c<='9'){
            int a = 0;
            while (i < s.size() && (s[i] >= '0' && s[i] <= '9')) {
                a = a * 10 + s[i] - '0';
                i++;
            }
            i--;
            vi.push(a * f);
        }else if(c=='(')vc.push(c);
        else if (c==')'){
            while(!vc.empty() && vc.top() != '(' ){
                int b=vi.top();
                vi.pop();
                int a=vi.top();
                vi.pop();
                char op=vc.top();
                vc.pop();
                if(op=='*')vi.push(a*b);
                if(op=='/')vi.push(a/b);
                if(op=='+')vi.push(a+b);
                if(op=='-')vi.push(a-b);
                if(op=='^')vi.push((int)(pow(a,b)));
            }
            vc.pop();
        }else if(c=='+'||c=='-'||c=='*'||c=='^'||c=='/'){
            while(!vc.empty() && vc.top()!='(' && ((c!='*' && vc.top()!='*' || vc.top()=='*')&&(c!='^' && vc.top()!='^' || vc.top()=='^')&&(c!='/' && vc.top()!='/' || vc.top()=='/'))){
                int b=vi.top();
                vi.pop();
                int a=vi.top();
                vi.pop();
                char op=vc.top();
                vc.pop();
                if(op=='*')vi.push(a*b);
                if(op=='/')vi.push(a/b);
                if(op=='+')vi.push(a+b);
                if(op=='-')vi.push(a-b);
                if(op=='^')vi.push((int)(pow(a,b)));
            }
            vc.push(c);
        }
    }
    while(!vc.empty()){
        int b=vi.top();
        vi.pop();
        int a=vi.top();
        vi.pop();
        char op=vc.top();
        vc.pop();
        if(op=='*')vi.push(a*b);
        if(op=='/')vi.push(a/b);
        if(op=='+')vi.push(a+b);
        if(op=='-')vi.push(a-b);
        if(op=='^')vi.push((int)(pow(a,b)));
    }
    cout<<vi.top()<<endl;

}

signed main() {



    int T=1;
    while(T--){
        solve();
    }
    return 0;
}