第四十一练 中缀表达式转后缀表达式

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

// 定义栈结构
typedef struct {
    int *data;
    int top;
    int capacity;
} Stack;

// 初始化栈
void initializeStack(Stack *stack, int capacity) {
    stack->data = (int *)malloc(sizeof(int) * capacity);
    stack->top = -1;
    stack->capacity = capacity;
}

// 判断栈是否为空
int isEmpty(Stack *stack) {
    return stack->top == -1;
}

// 判断栈是否已满
int isFull(Stack *stack) {
    return stack->top == stack->capacity - 1;
}

// 入栈操作
void push(Stack *stack, int element) {
    if (isFull(stack)) {
        printf("Stack overflow\n");
        return;
    }
    stack->data[++stack->top] = element;
}

// 出栈操作
int pop(Stack *stack) {
    if (isEmpty(stack)) {
        printf("Stack underflow\n");
        return -1;  // 返回-1表示栈已空
    }
    return stack->data[stack->top--];
}

// 计算后缀表达式的值
int evaluatePostfix(char *expression) {
    Stack stack;
    initializeStack(&stack, 100);  // 假设表达式不超过100个字符

    int length = strlen(expression);
    for (int i = 0; i < length; i++) {
        char current = expression[i];
        if (isdigit(current)) {
            // 如果是数字，入栈
            push(&stack, current - '0');
        } else if (current == ' ') {
            // 如果是空格，忽略
            continue;
        } else {
            // 如果是运算符，出栈两个数字进行运算，然后将结果入栈
            int operand2 = pop(&stack);
            int operand1 = pop(&stack);
            switch (current) {
                case '+':
                    push(&stack, operand1 + operand2);
                    break;
                case '-':
                    push(&stack, operand1 - operand2);
                    break;
                case '*':
                    push(&stack, operand1 * operand2);
                    break;
                case '/':
                    if (operand2 != 0) {
                        push(&stack, operand1 / operand2);
                    } else {
                        printf("Error: Division by zero\n");
                        return -1;  // 返回-1表示出现除零错误
                    }
                    break;
                default:
                    printf("Error: Invalid operator\n");
                    return -1;  // 返回-1表示出现无效运算符
            }
        }
    }

    // 返回最终结果
    return pop(&stack);
}

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

    int result = evaluatePostfix(expression);
    if (result != -1) {
        printf("Result: %d\n", result);
    }

    return 0;
}