C语言表达式求解

柔情只为你懂 2022-03-12 09:30 247阅读 0赞

**主要思路：**  
1. 将从键盘输入的中缀表达式转换成后缀表达式存放在一个结点p的字符串成员变量中；  
2. 利用后缀表达式进行表达式的计算，并将结果存入结点p的res成员变量中，最后将该结点以尾插的方式插入链表中；  
3. 遍历整个链表就得到所有表达式的结果了。  
**关键：**  
中缀到后缀表达式的转换以及后缀表达式的计算的关键在于对符号栈和操作数栈的使用。

/*-------------------------------------------------------------------------------------
    功能：实现表达式的计算，其中可包括+ - * / () 浮点数
    输入示例：
    3
    1+2+3+4+5+10
    2.2/3+100
    (56-40)/(4+2)
    输出示例：
    res = 25.0
    res = 100.7
    res = 2.7
    Author: Zhang Kaizhou
    Date: 2019-3-5 16:58:59
    ------------------------------------------------------------------------------------*/
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define MAXSIZE 1000
    
    typedef struct node{ // 定义一个Node数据类型，用于存放后缀表达式以及最终结果
        char post_str[MAXSIZE];
        double res;
        struct node * pnext;
    } Node;
    
    typedef struct{ // 定义一个字符栈数据类型
        char oper[MAXSIZE];
        int top_oper;
    } SqStack;
    
    typedef struct{ // 数据栈数据类型
        double data[MAXSIZE];
        int top_data;
    } DataStack;
    
    void in_to_post(char * in_str, Node * p);
    void compute_value(Node * p);
    void push_oper(SqStack * p_oper, char ch);
    void pop_oper(SqStack * p_oper, char * ch);
    void get_top_oper(SqStack * p_oper, char * ch);
    void push_data(DataStack * p_data, double num);
    void pop_data(DataStack * p_data, double * num);
    void get_top_data(DataStack * p_data, double * num);
    void list_tail_insert(Node ** pphead, Node ** pptail, Node * p);
    void list_print(Node * phead);
    
    int main(){
        char in_str[MAXSIZE];
        Node * phead = NULL, * ptail = NULL;
        int n, i;
    
        scanf("%d", &n);
        for(i = 0; i < n; i++){
            while(scanf("%s", in_str), getchar() != '\n'); // 每次从键盘读取一行字符串，以回车结束
            Node * pnew = (Node *)calloc(1, sizeof(Node));
            in_to_post(in_str, pnew);
            compute_value(pnew);
            list_tail_insert(&phead, &ptail, pnew);
        }
        list_print(phead);
    
        free(phead);
        free(ptail);
        return 0;
    }
    
    void in_to_post(char * in_str, Node * p){ // 将中缀表达式转换成后缀表达式
        SqStack * p_oper = (SqStack *)calloc(1, sizeof(SqStack)); // 定义一个栈指针，并初始化
        p_oper->top_oper = -1;
        int i = 0;
        char temp;
        while(* in_str != '\0'){
            switch(* in_str){
            case '(':
                push_oper(p_oper, '('); in_str++; break;
            case ')':
                pop_oper(p_oper, &temp);
                while(temp != '('){
                    p->post_str[i++] = temp;
                    pop_oper(p_oper, &temp);
                }
                in_str++; break;
            case '+':
            case '-':
                while(p_oper->top_oper >= 0){
                    get_top_oper(p_oper, &temp);
                    if(temp != '('){
                        p->post_str[i++] = temp;
                        pop_oper(p_oper, &temp);
                    }else{
                        break;
                    }
                }
                push_oper(p_oper, * in_str);
                in_str++; break;
            case '*':
            case '/':
                while(p_oper->top_oper >= 0){
                    get_top_oper(p_oper, &temp);
                    if(temp == '*' || temp == '/'){
                        p->post_str[i++] = temp;
                        pop_oper(p_oper, &temp);
                    }else{
                        break;
                    }
                }
                push_oper(p_oper, * in_str);
                in_str++; break;
            default:
                while((* in_str >= '0' && * in_str <= '9') || * in_str == '.'){
                    p->post_str[i++] = * in_str;
                    in_str++;
                }
                p->post_str[i++] = '#'; // 用#表示一个数字串结束
            }
        }
        while(p_oper->top_oper >= 0){
            pop_oper(p_oper, &temp);
            p->post_str[i++] = temp;
        }
        p->post_str[i] = '\0';
        free(p_oper); // 释放符号栈
    }
    
    void compute_value(Node * p){
        DataStack * p_data = (DataStack *)calloc(1, sizeof(DataStack)); // 定义一个操作数栈，并初始化
        p_data->top_data = -1;
        double temp1, temp2, num, res;
        int i = 0;
        char temp3[MAXSIZE];
        char * pcur = p->post_str;
        while(* pcur != '\0'){
            switch(* pcur){
            case '+':
                pop_data(p_data, &temp1);
                pop_data(p_data, &temp2);
                res = temp2 + temp1;
                push_data(p_data, res);
                break;
            case '-':
                pop_data(p_data, &temp1);
                pop_data(p_data, &temp2);
                res = temp2 - temp1;
                push_data(p_data, res);
                break;
            case '*':
                pop_data(p_data, &temp1);
                pop_data(p_data, &temp2);
                res = temp2 * temp1;
                push_data(p_data, res);
                break;
            case '/':
                pop_data(p_data, &temp1);
                pop_data(p_data, &temp2);
                if(temp1 != 0){
                    res = temp2 / temp1;
                    push_data(p_data, res);
                    break;
                }else{
                    printf("\n除零错误!\n");
                    exit(0);
                }
                break;
            default:
                num = 0;
                while((* pcur >= '0' && * pcur <= '9') || * pcur == '.'){
                    temp3[i++] = * pcur;
                    pcur++;
                }
                temp3[i] = '\0';
                num = atof(temp3); // 将数字串转换成浮点数
                i = 0;
                push_data(p_data, num);
                break;
            }
            pcur++;
        }
        get_top_data(p_data, &(p->res));
        return;
    }
    
    void push_oper(SqStack * p_oper, char ch){
        if(p_oper->top_oper == MAXSIZE - 1){
            printf("The operator stack is full!\n");
        }else{
            p_oper->top_oper++;
            p_oper->oper[p_oper->top_oper] = ch;
        }
        return;
    }
    
    void pop_oper(SqStack * p_oper, char * ch){
        if(p_oper->top_oper < 0){
            printf("The operator stack is empty!\n");
        }else{
            * ch = p_oper->oper[p_oper->top_oper];
            p_oper->top_oper--;
        }
        return;
    }
    
    void get_top_oper(SqStack * p_oper, char * ch){ // 取栈顶元素，但不移动栈顶指针
        if(p_oper->top_oper < 0){
            printf("The operator stack is empty!\n");
        }else{
            * ch = p_oper->oper[p_oper->top_oper];
        }
        return;
    }
    
    void push_data(DataStack * p_data, double num){
        if(p_data->top_data == MAXSIZE - 1){
            printf("The data stack is full!\n");
        }else{
            p_data->top_data++;
            p_data->data[p_data->top_data] = num;
        }
        return;
    }
    
    void pop_data(DataStack * p_data, double * num){
        if(p_data->top_data < 0){
            printf("The data stack is empty!\n");
        }else{
            * num = p_data->data[p_data->top_data];
            p_data->top_data--;
        }
        return;
    }
    
    void get_top_data(DataStack * p_data, double * num){
        if(p_data->top_data < 0){
            printf("The data stack is empty!\n");
        }else{
            * num = p_data->data[p_data->top_data];
        }
        return;
    }
    
    void list_tail_insert(Node ** pphead, Node ** pptail, Node * p){
        if(* pphead == NULL){
            * pphead = p;
            * pptail = p;
        }else{
            (* pptail)->pnext = p;
            * pptail = p;
        }
        return;
    }
    
    void list_print(Node * phead){
        while(phead != NULL){
            printf("\nres = %.1lf", phead->res);
            phead = phead->pnext;
        }
        return;
    }