题解 | #表达式求值#

双堆求值

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 返回表达式的值
 * @param s string字符串 待计算的表达式
 * @return int整型
 */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAXSIZE 100
struct stack_op {
    char data[MAXSIZE];
    int top;
};
struct stack_num {
    int data[MAXSIZE];
    int top;
};
void push(struct stack_op* stac, char temp) {
    if (stac->top != MAXSIZE - 1) {
        stac->data[++stac->top] = temp;
    }
}
void push_num(struct stack_num* stac, int temp) {
    if (stac->top != MAXSIZE - 1) {
        stac->data[++stac->top] = temp;
    }
}
void pop(struct stack_op* stac, char* temp) {
    if (stac->top != -1) {
        *temp = stac->data[stac->top--];
    }
}
void pop_num(struct stack_num* stac, int* temp) {
    if (stac->top != -1) {
        *temp = stac->data[stac->top--];
    }
}
int cal(int k1, int k2, char opt) {
    if (opt == '+') return k2 + k1;
    else if (opt == '-') return k2 - k1;
    else return k2 * k1;
}
int solve(char* s ) {
    //初始化
    struct stack_op* opt = (struct stack_op*)malloc(sizeof(struct stack_op));
    struct stack_num* num = (struct stack_num*)malloc(sizeof(struct stack_num));
    opt->top = -1;
    num->top = -1;
    int i = 0;
    //
    while (s[i] != '\0') {
        //判断当前值是否为数字
        if (s[i] >= '0' && s[i] <= '9') {
            int k = 0;
            while (s[i] != '\0' && s[i] >= '0' && s[i] <= '9') {
                k = k * 10 + (s[i] - '0');
                i++;
            }
            push_num(num, k);
        } else {
            //左括号
            if (s[i] == '(')
                push(opt, s[i]);
            //右括号，到做左括号为止
            else if (s[i] == ')') {
                char temp_opt = ')';
                while (opt->data[opt->top] != '(') {
                    int temp_num1;
                    int temp_num2;
                    pop_num(num, &temp_num1);
                    pop_num(num, &temp_num2);
                    pop(opt, &temp_opt);
                    push_num(num, cal(temp_num1, temp_num2, temp_opt));
                }
                pop(opt, &temp_opt);
            } else if (s[i] == '*') {
                push(opt, s[i]);
            } else {
                while (num->top >= 1) {
                    if (opt->data[opt->top] == '(')
                        break;
                    int temp_num1;
                    int temp_num2;
                    char temp_opt;
                    pop_num(num, &temp_num1);
                    pop_num(num, &temp_num2);
                    pop(opt, &temp_opt);
                    push_num(num, cal(temp_num1, temp_num2, temp_opt));
                }
                push(opt, s[i]);
            }
            i++;
        }
    }
    //最后可能的情况
    if (opt->top != -1) {
        int temp_num1;
        int temp_num2;
        char temp_opt;
        pop_num(num, &temp_num1);
        pop_num(num, &temp_num2);
        pop(opt, &temp_opt);
        push_num(num, cal(temp_num1, temp_num2, temp_opt));
    }
    int resul;
    pop_num(num, &resul);
    return resul;
}