栈及其应用之表达式求值

Question

任务描述
本关任务：编写从键盘输入一个算术表达式并输出它的结果的程序。

相关知识
为了完成本关任务，你需要掌握：栈的基本操作的实现，并能灵活运用栈特性，综合运用程序设计、算法分析等知识解决实际问题。
 表达式作为一个串存储，如表达式“32-(4+21)”,其求值过程为：自左向右扫描表达式，当扫描到32时不能马上计算，因后面可能还有更高的运算，正确的处理过程是：
需要两个栈：对象栈s_num和算符栈s_opt;自左至右扫描表达式, 若当前字符是运算对象，入s_num栈;对运算符，若这个运算符比栈顶运算符高则入栈，继续向后处理，若这个运算符比栈顶运算符低则从s_num栈出栈两个数，从栈s_opt出栈一运算符进行运算，并将其运算结果入s_num栈，继续处理当前字符，直到遇到结束符。 *

编程要求
根据提示，在右侧编辑器补充代码，计算并输出运算表达式的结果。

测试说明
平台会对你编写的代码进行测试：

测试输入：3*（5-2）；
预期输出：
9

开始你的任务吧，祝你成功！

Answer 1

原来写了一个，可以用一下 支持加减乘除 指数，浮点数，是以回车换行结束，中间不能有空格
测试如下
./htest
32-(4+21)
7
./htest
3*(5-2)*3
27

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define MAX_SIZE 100

#define EXP_DATA_INVALID 0
#define EXP_DATA_DOUBLE 1
#define EXP_DATA_INT 2
#define EXP_DATA_OP 3

char legel_letter[] = "1234567890.[]()+-*/^ ";
char legel_op[] = "[(+-*/^";

typedef struct _exp_data {
    union {
        double d_d;
        int    i_d;
        char   op;
    } u;
    int type;
} exp_data;

typedef struct _stack {
    exp_data *data;
    int top;
    int size;
} stack;

void init(stack *s)
{
    s->data = (exp_data *)malloc(sizeof(exp_data) * MAX_SIZE);
    s->size = MAX_SIZE;
    s->top = -1;
}

int empty(stack *s)
{
    return s->top == -1;
}

exp_data top(stack *s)
{
    exp_data invalid;
    invalid.type = EXP_DATA_INVALID;
    if (empty(s))
        return invalid;
    return s->data[s->top];
}

int push(stack *s, exp_data val)
{
    if (s == NULL || s->top + 1 == s->size)
        return 0;
    s->top += 1;
    s->data[s->top] = val;
    return 1;
}

int pop(stack *s)
{
    if (s == NULL || empty(s))
        return 0;
    s->top -= 1;
    return 1;
}

int judge_oper(char *str, char letter)
{
    char sub[1] = {0};
    char *p;
    sub[0] = letter;
    sub[1] = '\0';
    if(( p = strstr(str, sub)) == NULL) return 0;
    else return 1;
}

int get_op_number(char *str, exp_data *val)
{
    int i = 0;
    int flag_d_d = 0;
    char d_d_i[100] = {0};

    for (; (str[i]>= '0' && str[i] <= '9') || str[i] == '.'; i++) {
        if (str[i] == '.') flag_d_d = 1;
        d_d_i[i] = str[i];
    }
    if (i > 0) {
        if (flag_d_d) {
            val->u.d_d = strtod (d_d_i, NULL);
            val->type = EXP_DATA_DOUBLE;
        } else {
            val->u.i_d = strtod (d_d_i, NULL);
            val->type = EXP_DATA_INT;
        }
    }
    return i;
}

void do_op_number(stack *s, exp_data  val)
{
    exp_data top_1;
    exp_data top_2;
    char op;
    int flag_d_oper1 = 0;
    int flag_d_oper2 = 0;
    double d_d;

    if(empty(s)) {push(s, val); return;}

    top_1 = top(s);
    if (top_1.type != EXP_DATA_OP) { printf("error_1\n"); return; }
    op = top_1.u.op;

    if (op == '(' || op == '[') { push(s, val); return;}

    pop(s);
    top_2 = top(s);
    if (top_2.type == EXP_DATA_INVALID || top_2.type == EXP_DATA_OP) { printf("error_1\n"); return;}
    pop(s);
    if (top_2.type == EXP_DATA_DOUBLE) flag_d_oper2 = 1;
    if (val.type == EXP_DATA_DOUBLE) flag_d_oper1 = 1;
    switch(op) {
        case '+':
            d_d = (flag_d_oper2 ? top_2.u.d_d : top_2.u.i_d) + (flag_d_oper1?val.u.d_d : val.u.i_d);
            break;
        case '-':
            d_d = (flag_d_oper2 ? top_2.u.d_d : top_2.u.i_d) - (flag_d_oper1?val.u.d_d : val.u.i_d);
            break;
        case '*':
            d_d = (flag_d_oper2 ? top_2.u.d_d : top_2.u.i_d) * (flag_d_oper1?val.u.d_d : val.u.i_d);
            break;
        case '/':
            if ((flag_d_oper1?val.u.d_d : val.u.i_d) == 0) { printf("error_3\n"); return;}
            d_d = (flag_d_oper2 ? top_2.u.d_d : top_2.u.i_d) / (flag_d_oper1?val.u.d_d : val.u.i_d);
            break;
        case '^':
            d_d = pow((flag_d_oper2 ? top_2.u.d_d : top_2.u.i_d) , (flag_d_oper1?val.u.d_d : val.u.i_d));
            break;
    }
    if(flag_d_oper1 || flag_d_oper2) {
        val.type = EXP_DATA_DOUBLE;
        val.u.d_d = d_d;
        push(s, val);
    } else {
        val.type = EXP_DATA_INT;
        val.u.i_d = (int)d_d;
        push(s, val);
    }
}

void do_op_brackets(stack *s, char letter)
{
    exp_data top_1;
    exp_data top_2;

    top_1 = top(s);
    pop(s);

    //do (1+2)
    do_op_number(s, top_1);

    //do remove (1) and restore 1 to stack
    top_1 = top(s);
    pop(s);
    top_2 = top(s);
    pop(s);
    push(s, top_1);

    if ( letter == ')' ) {
        if (top_2.type != EXP_DATA_OP || top_2.u.op != '(') {
            printf("error_3\n");
            return ;
        }
    }
    if ( letter == ']' ) {
        if (top_2.type != EXP_DATA_OP || top_2.u.op != '[') {
            printf("error_3\n");
            return ;
        }
    }
}

int need_compute(char cur_op, char pre_op)
{
    //if (pre_op == '(' || pre_op == '[') return 0;
    if (cur_op == '+' || cur_op == '-') return 1;
    if (cur_op == '*' || cur_op == '/') {
        if (pre_op == '+' || pre_op == '-') return 0;
        else return 1;
    }
    if (cur_op == '^') return 0;
    return 1;
}

void do_push_op_brackets(stack *s, char letter)
{
    exp_data val;
    val.type = EXP_DATA_OP;
    val.u.op = letter;
    exp_data top_1, top_2, top_3;
    if (empty(s) || letter == '(' || letter == '[' || letter == '^') {
        if (push(s, val) == 0) { printf("push brackets error\n"); }
        return;
    }
    while(!empty(s)) {
        top_1 = top(s);
        pop(s);
        if(empty(s)) { push(s, top_1); push(s, val); return;}
        top_2 = top(s);
        if(top_2.type == EXP_DATA_OP && (top_2.u.op == '(' || top_2.u.op == '[')) {
            push(s, top_1); push(s, val); return;
        }
        pop(s);
        if(empty(s)) { push(s, top_2); push(s, top_1); push(s, val); return;}
        top_3 = top(s);
        pop(s);
        if (top_2.type != EXP_DATA_OP) { printf("error_3\n"); return; }
        if (need_compute(letter, top_2.u.op)) {
            push(s, top_3); push(s, top_2);
            do_op_number(s, top_1);
        } else {
            push(s, top_3); push(s, top_2); push(s, top_1);
            push(s, val);
            return;
        }
    }
    push(s, val);
}

void do_compute(char *exp)
{
    stack s;
    exp_data val;
    int i = 0, jump = 0;
    char letter;
    init(&s);
    letter = exp[i];
    while(letter != '\0') {
        if (judge_oper(legel_letter, letter) == 0) { printf("error_0\n"); break;}
        if (judge_oper(legel_op, letter)) { do_push_op_brackets(&s, letter); }
        if (letter == ')' || letter == ']') { do_op_brackets(&s, letter); }
        if (letter == '.' && (i == 0 || exp[i-1] > '9' || exp[i-1] < '0')) {printf("error_00\n"); break;}
        if ((letter >= '0' && letter <= '9') || letter == '.') {
            jump = get_op_number(&exp[i], &val);
            if (!jump) { printf("error_000\n"); break;}
            push(&s, val);
            i+=jump;
            jump = 0;
        } else i++;
        letter = exp[i];
    }

    if(empty(&s)) { printf("error_30\n"); goto err; }

    exp_data top_1, top_2;
    while(!empty(&s) && s.top >= 2) {
        top_1 = top(&s);
        pop(&s);
        do_op_number(&s, top_1);
    }

    //do last result
    top_1 = top(&s);
    pop(&s);
    if (!empty(&s))  { printf("error_300\n"); goto err; }

    if  (top_1.type == EXP_DATA_OP) printf("error_3000\n");
    else {
        if (top_1.type == EXP_DATA_DOUBLE) printf("%lf\n", top_1.u.d_d);
        else printf("%d\n", top_1.u.i_d);
    }
err:
    if (s.data) free(s.data);
}

int main()
{
   char exp[100];
   scanf("%s", exp);
   do_compute(exp);
   return 0;
}