1356：计算(calc)

时间限制: 1000 ms 内存限制: 65536 KB
提交数: 5424 通过数: 2105

【题目描述】
小明在你的帮助下，破密了Ferrari设的密码门，正要往前走，突然又出现了一个密码门，门上有一个算式，其中只有“(”，“)”，“0-9”，“+”，“-”，“*”，“/”，“^”，求出的值就是密码。小明数学学得不好，还需你帮他的忙。(“/”用整数除法)

【输入】
共1行，为一个算式。

【输出】
共1行，就是密码。

【输入样例】
1+(3+2)(7^2+69)/(2)
【输出样例】
258

#include <iostream>
#include <stack>
#include <string>
#include <cmath>
using namespace std;

stack <long long> S1;
stack <long long> S2;


int main() {
    string exp;
    cin>>exp;
    int num=0;
    bool f=false;
    for(long long i=0; i<exp.length(); i++) {
        if(!(exp[i]>='0' && exp[i]<='9')) {
            if(f) {
                S2.push(num+256);
                num=0;
                f=false;
            }
        }
        if(exp[i]>='0' && exp[i]<='9') {
            num=num*10+(exp[i]-'0');
            f=true;
        } else if(exp[i]=='(' || S1.empty())
            S1.push(exp[i]);
        else if(exp[i]==')') {
            while(S1.top()!='(') {
                S2.push(S1.top());
                S1.pop();
            }
            S1.pop();
        } else {
            if(exp[i]=='-' || exp[i]=='+') {
                while(!(S1.empty() || S1.top()=='(')) {
                    S2.push(S1.top());
                    S1.pop();
                }
                S1.push(exp[i]);
            } else if(exp[i]=='*' || exp[i]=='/') {
                while(!(S1.empty() || S1.top()=='(' || S1.top()=='+' || S1.top()=='-')) {
                    S2.push(S1.top());
                    S1.pop();
                }
                S1.push(exp[i]);
            } else if (exp[i]=='^') {
                while(!(S1.empty() || S1.top()=='(' || S1.top()=='+' || S1.top()=='-' || S1.top()=='*' || S1.top()=='/')) {
                    S2.push(S1.top());
                    S1.pop();
                }
                S1.push(exp[i]);
            }
        }
    }
    if(f) {
        S2.push(num+256);
        num=0;
        f=false;
    }
    while(!S1.empty()) {
        S2.push(S1.top());
        S1.pop();
    }
    while(!S2.empty()) {
        S1.push(S2.top());
        S2.pop();
    }
    stack <long long> ans;
    while(!S1.empty()) {

        if(S1.top()>=256)
            ans.push(S1.top()-256);
        else {
            char oper=S1.top();
            long long a,b;
            a=ans.top();
            ans.pop();
            b=ans.top();
            ans.pop();

            long long ret=0;
            switch(oper) {
                case '+':
                    ret=a+b;
                    break;
                case '-':
                    ret=b-a;
                    break;
                case '*':
                    ret=a*b;
                    break;
                case '/':
                    ret=b/a;
                    break;
                case '^':
                    ret=pow(b,a);
                    break;
            }
            ans.push(ret);
        }
        S1.pop();
    }
    cout<<ans.top();
}