第四十四练 请以递归方式实现计算阶乘的函数

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

// 定义栈结构
#define MAX_SIZE 100
typedef struct {
    int top;
    double items[MAX_SIZE];
} Stack;

// 初始化栈
void initialize(Stack* stack) {
    stack->top = -1;
}

// 检查栈是否为空
int is_empty(const Stack* stack) {
    return stack->top == -1;
}

// 将元素压入栈
void push(Stack* stack, double value) {
    if (stack->top == MAX_SIZE - 1) {
        printf("Stack overflow\n");
        exit(EXIT_FAILURE);
    }
    stack->items[++stack->top] = value;
}

// 弹出栈顶元素
double pop(Stack* stack) {
    if (is_empty(stack)) {
        printf("Stack underflow\n");
        exit(EXIT_FAILURE);
    }
    return stack->items[stack->top--];
}

// 获取栈顶元素
double peek(const Stack* stack) {
    if (is_empty(stack)) {
        printf("Stack is empty\n");
        exit(EXIT_FAILURE);
    }
    return stack->items[stack->top];
}

// 判断运算符的优先级
int precedence(char operator) {
    if (operator == '+' || operator == '-') {
        return 1;
    } else if (operator == '*' || operator == '/') {
        return 2;
    }
    return 0;
}

// 将中缀表达式转换为后缀表达式
void infix_to_postfix(const char* infix, char* postfix) {
    Stack operator_stack;
    initialize(&operator_stack);

    int i = 0, j = 0;

    while (infix[i] != '\0') {
        if (isdigit(infix[i]) || infix[i] == '.') {
            while (isdigit(infix[i]) || infix[i] == '.') {
                postfix[j++] = infix[i++];
            }
            postfix[j++] = ' ';
        } else if (infix[i] == '(') {
            push(&operator_stack, infix[i++]);
        } else if (infix[i] == ')') {
            while (!is_empty(&operator_stack) && peek(&operator_stack) != '(') {
                postfix[j++] = pop(&operator_stack);
                postfix[j++] = ' ';
            }
            if (!is_empty(&operator_stack) && peek(&operator_stack) == '(') {
                pop(&operator_stack); // 弹出左括号
            }
            i++;
        } else if (infix[i] == '+' || infix[i] == '-' || infix[i] == '*' || infix[i] == '/') {
            while (!is_empty(&operator_stack) && precedence(peek(&operator_stack)) >= precedence(infix[i])) {
                postfix[j++] = pop(&operator_stack);
                postfix[j++] = ' ';
            }
            push(&operator_stack, infix[i++]);
        } else {
            // 忽略空格等其他字符
            i++;
        }
    }

    while (!is_empty(&operator_stack)) {
        postfix[j++] = pop(&operator_stack);
        postfix[j++] = ' ';
    }

    postfix[j] = '\0';
}

// 计算后缀表达式的值
double evaluate_postfix(const char* postfix) {
    Stack operand_stack;
    initialize(&operand_stack);

    int i = 0;

    while (postfix[i] != '\0') {
        if (isdigit(postfix[i]) || postfix[i] == '.') {
            double operand = atof(&postfix[i]);
            push(&operand_stack, operand);
            while (isdigit(postfix[i]) || postfix[i] == '.') {
                i++;
            }
        } else if (postfix[i] == ' ') {
            i++;
        } else {
            double operand2 = pop(&operand_stack);
            double operand1 = pop(&operand_stack);

            switch (postfix[i]) {
                case '+':
                    push(&operand_stack, operand1 + operand2);
                    break;
                case '-':
                    push(&operand_stack, operand1 - operand2);
                    break;
                case '*':
                    push(&operand_stack, operand1 * operand2);
                    break;
                case '/':
                    if (operand2 == 0) {
                        printf("Error: Division by zero\n");
                        exit(EXIT_FAILURE);
                    }
                    push(&operand_stack, operand1 / operand2);
                    break;
                default:
                    printf("Error: Invalid operator\n");
                    exit(EXIT_FAILURE);
            }

            i++;
        }
    }

    return pop(&operand_stack);
}

int main() {
    char infix_expression[100];
    printf("Enter an expression: ");
    fgets(infix_expression, sizeof(infix_expression), stdin);

    char postfix_expression[100];
    infix_to_postfix(infix_expression, postfix_expression);
    printf("Postfix expression: %s\n", postfix_expression);

    double result = evaluate_postfix(postfix_expression);
    printf("Result: %lf\n", result);

    return 0;
}