题解 | #计算表达式#

使用两个辅助栈，一个保存运算数字，一个保存运算符 需要注意的是栈元素使用float保存，输出的时候只输出整数部分

#include <cstdio>
#include <cstring>
#include <string>
#include <stack>
#include <cctype>
#include <iostream>

using namespace std;
string str;
stack<float> nums;
stack<char> ops;

int getNum(int left, int &i_new){
    int right = left;
    int res = 0, base = 1;
    while(isdigit(str[right]))
        right++;

    i_new = right;
    right--;

    while(right >= left){
        res += base * (str[right] - '0');
        base *= 10;
        right--;
    }
    
    // printf("Get Num: %d \n", res);
    return res;
    
}

int priority(char ch){
    if(ch == '#')
        return 0;
    if(ch == '$')
        return 1;
    if(ch == '+' || ch == '-')
        return 2;
    else
        return 3;
    
}

void calculate(char op, char top){
    float right, left;
    float sum=0;
    
    while(priority(top) >= priority(op)){
        right = nums.top();
        nums.pop();
        left = nums.top();
        nums.pop();
        
        if(top == '+'){
            sum = left + right;
        }else if(top == '-'){
            sum = left - right;
        }else if(top == '*'){
            sum = (1.0)*left * right;
        }else{
            sum = (1.0)*left/right;
        }
        nums.push(sum);
        ops.pop();
        top = ops.top();
    }
    ops.push(op);
}

int main(void){
    

    char op, top;
    while(getline(cin, str)){
        while (!nums.empty())
        {
            nums.pop();
        }
        while(!ops.empty()){
            ops.pop();
        }
        
        int i=0, num, left, right;
        ops.push('#');
        str = str + "$";
        while(i<str.size()){
            if(isdigit(str[i])){
                num = getNum(i, i);
                nums.push(num);
            }else{
                op = str[i++];
                top = ops.top();
                
                if(priority(op) > priority(top)){
                    // 如果当前运算符比栈顶运算符高，入栈
                    ops.push(op);
                }else{
                    //运算，直到栈顶低于当前运算符
                    calculate(op, top);
                }
            }
        }
        printf("%d\n", (int)nums.top());
    }
    
    
    return 0;
}