小鸡计算器

简要题面

给定一个包含+ - * / ( ) 的表达式，输出运算结果

题面

被聪明的参赛者们打开了第一个宝箱后，小鸡发誓要夺回属于她的一切！

她翻开珍藏的魔法书，虔诚地召唤出伟大的神明。神明被她的执着打动，赐予了一个能够帮助她找回丢失宝藏的神奇法宝。不过，这个法宝被施加了层层禁制，需要逐一解开才能激活。

此刻，法宝周围浮现出一串串神秘的数字算式。小鸡明白，只有正确解出所有的算式，才能彻底激活法宝，最终找回失落的宝藏。然而，长时间没有动脑筋的小鸡，已经对这些数字感到力不从心。于是，她决定寻求善良的你的帮助，助她一臂之力，破解谜题，激活法宝，找回属于她的宝藏！

输入描述

一行一个包含 + - * / ( ) 的表达式，保证表达式合法并且数字不含负数。

输出描述

一行一个数字表示表达式的值

若结果不为整数，请用最简分数表示

输入输出样例

输入 #1

6*5/2-(3+8)

输出 #1

4

输入 #2

3/(2-8)

输出 #2

-1/2

说明/提示

题目只保证初始表达式中不含负数，计算过程中可能出现负数。

解法

计算表达式时，我们维护两个栈：

• 数值栈 num：存储当前的数值（分数形式 pair<分子, 分母>）。
• 运算符栈 op：存储当前的操作符 + - * / 和括号 ()。

计算规则：

1. 遇到数字：解析完整数字后，将其压入 num 栈，默认分母为 1（整数）。
2. 遇到运算符 + - * /：
   • 若运算符栈 op 非空，并且栈顶运算符的优先级不低于当前运算符，则先计算栈顶运算，直到遇到低优先级的运算符或 (。
   • 之后再将当前运算符入栈。
3. 遇到 (：直接入 op 栈。
4. 遇到 )：
   • 依次执行 op 栈中的运算，直到匹配到 (，然后弹出 (。
5. 处理剩余的运算：遍历结束后，栈中可能仍有运算符，需要依次弹出执行，直到 op 为空。

由于 * / 可能会产生分数，需要实现分数的四则运算，并保证最简分数表示：

• 加法：

  $\frac{a}{b} + \frac{c}{d} = \frac{a \times d + b \times c}{b \times d}$

• 减法： $\frac{a}{b} - \frac{c}{d} = \frac{a \times d - b \times c}{b \times d}$

• 乘法： $\frac{a}{b} \times \frac{c}{d} = \frac{a \times c}{b \times d}$

• 除法： $\frac{a}{b} \div \frac{c}{d} = \frac{a \times d}{b \times c}$

• 计算后需求 最大公因数（gcd），将分数化为最简形式。

参考程序

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
stack<pair<ll,ll>> num;
stack<char> op;
map<char,int> mp;
pair<ll,ll> mul(pair<ll,ll> a,pair<ll,ll> b){
    ll fz=a.first*b.first;
    ll fm=a.second*b.second;
    ll gcd=__gcd(fz,fm);
    fz/=gcd;
    fm/=gcd;
    return {fz,fm};
}
pair<ll,ll> div(pair<ll,ll> a,pair<ll,ll> b){
    ll fz=a.first*b.second;
    ll fm=a.second*b.first;
    ll gcd=__gcd(fz,fm);
    fz/=gcd;
    fm/=gcd;
    return {fz,fm};
}
pair<ll,ll> add(pair<ll,ll> a,pair<ll,ll> b){
    ll fz=a.first*b.second+a.second*b.first;
    ll fm=a.second*b.second;
    ll gcd=__gcd(fz,fm);
    fz/=gcd;
    fm/=gcd;
    return {fz,fm};
}
pair<ll,ll> sub(pair<ll,ll> a,pair<ll,ll> b){
    ll fz=a.first*b.second-a.second*b.first;
    ll fm=a.second*b.second;
    ll gcd=__gcd(fz,fm);
    fz/=gcd;
    fm/=gcd;
    return {fz,fm};
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    ll temp=0;
    mp['(']=mp[')']=0;
    mp['+']=mp['-']=1;
    mp['*']=mp['/']=2;
    string s;
    cin>>s;
    for(int i=0;i<s.length();i++){
        if(s[i]>='0'&&s[i]<='9'){
            temp*=10;
            temp+=s[i]-'0';
        }
        else{
            if(i>0&&s[i-1]>='0'&&s[i-1]<='9'){
                num.push({temp,1});
                temp=0;
            }
            if(s[i]=='(') op.push(s[i]);
            else if(s[i]==')'){
                while(op.top()!='('){
                    pair<ll,ll> a=num.top();
                    num.pop();
                    pair<ll,ll> b=num.top();
                    num.pop();
                    if(op.top()=='*') num.push(mul(b,a));
                    else if(op.top()=='/') num.push(div(b,a));
                    else if(op.top()=='+') num.push(add(b,a));
                    else num.push(sub(b,a));
                    op.pop();
                }
                op.pop();
            }
            else{
                while(!op.empty()&&(mp[op.top()]>=mp[s[i]])){
                    pair<ll,ll> a=num.top();
                    num.pop();
                    pair<ll,ll> b=num.top();
                    num.pop();
                    if(op.top()=='*') num.push(mul(b,a));
                    else if(op.top()=='/') num.push(div(b,a));
                    else if(op.top()=='+') num.push(add(b,a));
                    else num.push(sub(b,a));
                    op.pop();
                }
                op.push(s[i]);
            }
        }
    }
    if(s[s.length()-1]>='0'&&s[s.length()-1]<='9') num.push({temp,1});
    while(!op.empty()){
        pair<ll,ll> a=num.top();
        num.pop();
        pair<ll,ll> b=num.top();
        num.pop();
        if(op.top()=='*') num.push(mul(b,a));
        else if(op.top()=='/') num.push(div(b,a));
        else if(op.top()=='+') num.push(add(b,a));
        else num.push(sub(b,a));
        op.pop();
    }
    pair<ll,ll> ans=num.top();
    if(ans.second<0){
        ans.first=-ans.first;
        ans.second=-ans.second;
    }
    if(ans.second==1) cout<<ans.first<<'\n';
    else cout<<ans.first<<'/'<<ans.second<<'\n';
    return 0;
}