算法训练 表达式计算

问题描述

输入一个只包含加减乖除和括号的合法表达式，求表达式的值。其中除表示整除。

输入格式

输入一行，包含一个表达式。

输出格式

输出这个表达式的值。

样例输入

1-2+3*(4-5)

样例输出

-4

数据规模和约定

表达式长度不超过100，表达式运算合法且运算过程都在int内进行。

利用栈和后缀表达式来做

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

char *infix2postfix(char *exp) {
    char *postExp = new char[200];
    int cnt = 0;
    stack<char> st;
    for(int i = 0; i < strlen(exp); i++) {
        if(isdigit(exp[i])) {
            postExp[cnt++] = exp[i];
        } else {
            if(isdigit(postExp[cnt-1])) {
                postExp[cnt++] = '#';
            }
            if(exp[i] == '+' || exp[i] == '-') {
                if(!st.empty()) {
                    while(!st.empty() && st.top() != '(') {
                        postExp[cnt++] = st.top();
                        st.pop();
                    }
                }
                st.push(exp[i]);
            } else if(exp[i] == '*' || exp[i] == '/' || exp[i] == '(') {
                st.push(exp[i]);
            } else if(exp[i] == ')') {
                while(st.top() != '(') {
                    postExp[cnt++] = st.top();
                    st.pop();
                }
                st.pop();
            }
        }
    } 
    while(!st.empty()) {
        postExp[cnt++] = st.top();
        st.pop();
    }
    
    postExp[cnt] = 0;
    return postExp;
} 

int calculate(char *post) {
    int ans = 0;
    int a, b;
    stack<int> st;
    for (int i = 0; i < strlen(post); i++) {
        a = b = 0;
        if(isdigit(post[i])) {
            while(isdigit(post[i])) {
                b = post[i] - '0';
                a = a * 10 + b;
                i++;
            }
            if(post[i] != '#')
                i--;
            //cout << a << endl; 
            st.push(a);
        } else {
            a = st.top();
            st.pop();
            b = st.top();
            st.pop();
            switch(post[i]) {
                case '+':
                    ans = a + b;    
                    break;
                case '-':
                    ans = b - a;
                    break;
                case '*':
                    ans = a * b;
                    break;
                case '/':
                    ans = b / a;
                    break;
            }
            //cout << ans << endl;
            st.push(ans);
        }
    }
    
    return ans;
}

int main() {
    char exp[101];
    char *postExp = new char[200];
    scanf("%s", exp);
    postExp = infix2postfix(exp);
    //printf("%s\n", postExp);
    printf("%d\n", calculate(postExp));
    
    return 0;
}