#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <ctype.h>

#include <math.h> // 如果需要使用pow函数，需要包含math.h头文件



#define MAX_STACK_SIZE 100 // 栈的最大容量

#define MAX_EXPR_SIZE 100 // 表达式的最大长度



typedef struct {

    double data[MAX_STACK_SIZE];

    int top;

} Stack;



// 初始化栈

void initStack(Stack* s) {

    s->top = -1;

}



// 判断栈是否为空

int isStackEmpty(Stack* s) {

    return s->top == -1;

}



// 判断栈是否已满

int isStackFull(Stack* s) {

    return s->top == MAX_STACK_SIZE - 1;

}



// 元素入栈

void push(Stack* s, double data) {

    if (isStackFull(s)) {

        printf("Stack overflow!\n");

        exit(1);

    }

    s->data[++s->top] = data;

}



// 元素出栈

double pop(Stack* s) {

    if (isStackEmpty(s)) {

        printf("Stack underflow!\n");

        exit(1);

    }

    return s->data[s->top--];

}



// 获取栈顶元素

double peek(Stack* s) {

    if (isStackEmpty(s)) {

        printf("Stack underflow!\n");

        exit(1);

    }

    return s->data[s->top];

}



// 判断是否为运算符

int isOperator(char c) {

    return c == '+' || c == '-' || c == '*' || c == '/' || c == '(' || c == ')';

}



// 获取运算符优先级

int getPriority(char c) {

    switch (c) {

        case '+':

        case '-':

            return 1;

        case '*':

        case '/':

            return 2;

        default:

            return 0;

    }

}



// 中缀表达式转后缀表达式

void infixToPostfix(char* infix, char* postfix) {

    Stack opStack; // 运算符栈

    initStack(&opStack);



    int n = strlen(infix);

    char numStr[MAX_EXPR_SIZE]; // 用来存放数字字符串

    int k = 0; // postfix的下标



    for (int i = 0; i < n; i++) {

        char c = infix[i];



        if (isdigit(c) || c == '.') {

            // 如果是数字，则将其添加到数字字符串中

            numStr[k++] = c;

        } else if (isOperator(c)) {

            // 如果是运算符

            if (k > 0) {

                // 如果数字字符串不为空，说明前面有数字，需要将其添加到后缀表达式中

                numStr[k] = '\0';

                strcat(postfix, numStr); // 添加数字字符串

                strcat(postfix, " "); // 添加空格，用于后续判断数字的结束位置

                k = 0;

            }



            if (c == '(') {

                push(&opStack, c);

            } else if (c == ')') {

                while (!isStackEmpty(&opStack) && peek(&opStack) != '(') {

                    char op = pop(&opStack);

                    char str[2] = {op, '\0'};

                    strcat(postfix, str);

                    strcat(postfix, " ");

                }

                pop(&opStack); // 弹出左括号

            } else {

                while (!isStackEmpty(&opStack) && getPriority(c) <= getPriority(peek(&opStack))) {

                    char op = pop(&opStack);

                    char str[2] = {op, '\0'};

                    strcat(postfix, str);

                    strcat(postfix, " ");

                }

                push(&opStack, c);

            }

        } else {

            printf("Invalid character: %c\n", c);

            exit(1);

        }

    }



    // 将剩余的数字添加到后缀表达式中

    if (k > 0) {

        numStr[k] = '\0';

        strcat(postfix, numStr);

        strcat(postfix, " ");

    }



    // 将剩余的运算符添加到后缀表达式中

    while (!isStackEmpty(&opStack)) {

        char op = pop(&opStack);

        char str[2] = {op, '\0'};

        strcat(postfix, str);

        strcat(postfix, " ");

    }

}



// 后缀表达式求值

double evaluatePostfix(char* postfix) {

    Stack numStack; // 数字栈

    initStack(&numStack);



    char* token = strtok(postfix, " ");

    while (token != NULL) {

        if (strlen(token) == 1 && isOperator(token[0])) {

            // 如果是运算符

            double num2 = pop(&numStack);

            double num1 = pop(&numStack);



            switch (token[0]) {

                case '+':

                    push(&numStack, num1 + num2);

                    break;

                case '-':

                    push(&numStack, num1 - num2);

                    break;

                case '*':

                    push(&numStack, num1 * num2);

                    break;

                case '/':

                    if (num2 == 0) {

                        printf("Divide by zero error!\n");

                        exit(1);

                    }

                    push(&numStack, num1 / num2);

                    break;

                default:

                    break;

            }

        } else {

            // 如果是数字

            double num;

            sscanf(token, "%lf", &num);

            push(&numStack, num);

        }

        token = strtok(NULL, " ");

    }



    return pop(&numStack); // 最后栈中只剩下一个元素，即为表达式的最终结果

}



// 计算表达式的函数

double calcExpression(char* expr) {

    char postfix[MAX_EXPR_SIZE] = "";

    infixToPostfix(expr, postfix);

#ifdef _DEBUG

    printf("中缀转后缀表达式：%s\n", postfix);

#endif

    return evaluatePostfix(postfix);

}



int main() {

    char expr[MAX_EXPR_SIZE];



    printf("请输入四则运算表达式：\n");

    fgets(expr, MAX_EXPR_SIZE, stdin);

    expr[strlen(expr) - 1] = '\0';



    double result = calcExpression(expr);

    printf("计算结果为：%.2f\n", result);



    return 0;

}