题解 | #表达式求值#

#include<stdio.h>
#include<stdbool.h>
//将‘-’‘1‘‘0’变成-10
int chartonum(char* str, int i, int j) {
    bool neg = false;
    if (str[i] == '-') {
        neg = true;
        i++;
    }
    int res = str[i] - '0';
    while (++i <= j) {
        res = res * 10 + str[i] - '0';
    }
    return neg ? -1 * res : res;
}
//计算一个最简表达式如100*-500,-3,(-100)
int solveone(char* str, int i, int j) { 
    if (str[i] == '(' && str[j] == ')') return chartonum(str, i + 1, j - 1);
    int k = i + 1;
    while (k<j&&str[k] != '+' && str[k] != '-' && str[k] != '*' && str[k] != '/')k++;
    if (k == j)return chartonum(str, i, j);//-3
    int L = chartonum(str, i, k - 1), R = chartonum(str, k + 1, j);
    return str[k] == '+' ? L + R : str[k] == '-' ? L - R : str[k] == '*' ? L * R : L / R;
}
void cal(char* str, int i, int j) {//计算字符串i到j的部分，并将结果填回字符串
    int res = solveone(str, i, j);
    bool neg=false,sig=false;//neg该数是否为负，sig是否要添加‘+’或‘-’
    if (res <= 0) {
        res = -1 * res;
        neg = true;
        sig = true;
    }
    else 
        if (i > 0 && str[i - 1] != '(' && str[i - 1] >= '0' && str[i - 1] <= '9')sig = true;
    int len = 1,res1=res;
    while (res1 /= 10)len++;
    len += sig;//考虑符号占一位
    char t[32];//备份原字符串j后内容
    int k = 0;
    while (str[j + k+1]) {
        t[k] = str[j + k+1];
        k++;
    }
    t[k] = 0;
    int len1 = len;
    while (len1>1) {//最前面一个字符可能是符号，留一手
        str[i+len1-1] = res % 10+'0';
        res /= 10;
        len1--;
    }
    str[i] = sig ? neg? '-' :'+': res + '0';
    while (k >= 0) {
        str[i + len + k] = t[k];
        k--;
    }
}
void calop(char* str, int op) {//以运算符op为中心，计算一个单目表达式
    int i = op - 1, j = op + 2;
    while (str[j]&&str[j] >= '0' && str[j] <= '9')j++;
    j--;
    while (i>=0&& str[i] >= '0' && str[i] <= '9')i--;
    if (i<0||str[i] != '-')i++;
    cal(str, i, j);
}
bool calbra(char* str, int i, int j) {//计算一次左右括号分别在i和j的部分，更新字符串,返回是否消除此括号
    int plus = i, mul = i;//寻找两类运算符
    for (int k = j-1; k >=i+2; k--)
        if (str[k] == '+' || str[k] == '-')
            plus = k;
        else if (str[k] == '*' || str[k] == '/')
            mul = k;
    if (mul - i)
        calop(str, mul);
    else if (plus - i)
        calop(str, plus);
    else {
        if(i!=-1)cal(str, i, j);
        return true;
    }
    return false;
}
int main() {
    char str[101]="4+(6*(4*7-9*(0-8-4)*2))";
    while (~scanf("%s", str)) {
        int i=-1,j;
        while (1) {
            j = 0;
            while (str[j] && str[j] != ')')j++;
            if (str[j] == 0)break;
            for (i = j; i >= 0 && str[i] != '('; i--);
            calbra(str, i, j);
        }
        do {
            j = 0;
            while (str[j])j++;
        } while (!calbra(str, -1, j));
        if (str[0] == '-' && str[1] == '0' && str[2] == 0)
            printf("0\n");
        else
            printf("%s\n", str);
    }
}