算法训练 表达式计算

#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <cctype>

using namespace std;

stack<int> stack_num;
stack<char> stack_op;

bool f(char ch1, char ch2){
    // 1-2+3     1*2/3
    if ((ch1 == '-'||ch1 == '+') && (ch2 == '+'|| ch2 == '-') )
        return false;
    if ((ch1 == '*' || ch1 == '/') && (ch2 == '*' || ch2 == '/'))
        return false;

    // 1*2-3
    if ((ch1 == '*' || ch1 == '/') && (ch2 == '+' || ch2 == '-'))
        return false;

    // 1+2*3
    if ((ch1 == '+' || ch1 == '-') && (ch2 == '*' || ch2 == '/'))
        return true;
}

int calc(int num1, int num2, char op){
    int ret = 0;
    switch (op)
    {
    case '+': ret = num1 + num2; break;
    case '-': ret = num1 - num2; break;
    case '*': ret = num1 * num2; break;
    case '/': ret = num1 / num2; break;
    default:
        break;
    }
    return ret;
}
// 5*((1-2)*(6-7+8*9-(34-12*1)))
// 1-2+3*(4-5)
int main(){
    string str;
    cin >> str;

    for (unsigned int i = 0; i < str.length(); i++){
        if (isdigit(str[i])){
            string tmp = "";
            stringstream ss;
            int k;
            while (isdigit(str[i])){
                tmp += str[i];
                i++;
            }
            i-=1;
            ss << tmp;
            ss >> k;
            stack_num.push(k);
        }else{
            if (stack_op.empty() || str[i] == '('){
                stack_op.push(str[i]);
            }else{
                if (str[i] == ')'){
                   while (stack_op.top() != '(')
                   {
                       int num1, num2;
                       if (!stack_num.empty()){
                           num2 = stack_num.top();
                           stack_num.pop();
                       }else{
                           num2 = 0;
                       }
                       if (!stack_num.empty()){
                           num1 = stack_num.top();
                           stack_num.pop();
                       }else{
                           num1 = 0;
                       }
                       char op = stack_op.top();
                       stack_op.pop();
                       stack_num.push(calc(num1, num2, op));
                   }
                   stack_op.pop(); // 除去stack_op 中的 (
                }else{
                    char ch1 = stack_op.top();
                    char ch2 = str[i];
                    if (f(ch1, ch2)){
                        stack_op.push(str[i]);
                    }else{
                        int num2 = stack_num.top();
                        stack_num.pop();
                        int num1 = stack_num.top();
                        stack_num.pop();
                        int s = calc(num1, num2, stack_op.top());
                        stack_op.pop();
                        stack_num.push(s);
                        stack_op.push(str[i]);
                    } // end if (f(ch1,ch2))
                }
            }
        }
    }

    // 清空尾数据
    while (!stack_op.empty()){
        int num1, num2;
        if (!stack_num.empty()){
            num2 = stack_num.top();
            stack_num.pop();
        }else{
            num2 = 0;
        }
        if (!stack_num.empty()){
            num1 = stack_num.top();
            stack_num.pop();
        }else{
            num1 = 0;
        }
        char op = stack_op.top();
        stack_op.pop();
        stack_num.push(calc(num1, num2, op));
    }
    cout << stack_num.top() << endl;
    return 0;
}