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

#define MAX_STACK_SIZE 100
#define MAX_TOKEN_LENGTH 10

// 定义顺序栈结构
typedef struct {
    double data[MAX_STACK_SIZE];
    int top;
} Stack;

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

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

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

// 入栈操作
int push(Stack *s, double value) {
    if (isFull(s)) {
        printf("错误：栈溢出\n");
        return 0;
    }
    s->data[++(s->top)] = value;
    return 1;
}

// 出栈操作
int pop(Stack *s, double *value) {
    if (isEmpty(s)) {
        printf("错误：栈为空\n");
        return 0;
    }
    *value = s->data[(s->top)--];
    return 1;
}

// 获取栈顶元素
int peek(Stack *s, double *value) {
    if (isEmpty(s)) {
        printf("错误：栈为空\n");
        return 0;
    }
    *value = s->data[s->top];
    return 1;
}

// 判断是否为运算符
int isOperator(char *token) {
    return strcmp(token, "+") == 0 || 
           strcmp(token, "-") == 0 || 
           strcmp(token, "*") == 0 || 
           strcmp(token, "/") == 0;
}

// 应用运算符进行计算
double applyOp(double a, double b, char op) {
    switch(op) {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/': 
            if (b == 0) {
                printf("错误：除数不能为零\n");
                exit(EXIT_FAILURE);
            }
            return a / b;
        default: 
            printf("错误：不支持的运算符 %c\n", op);
            exit(EXIT_FAILURE);
    }
}

// 计算逆波兰表达式
double evaluateRPN(char *tokens[], int tokenCount) {
    Stack stack;
    initStack(&stack);
    
    for (int i = 0; i < tokenCount; i++) {
        // 如果是数字，转换为double并压入栈
        if (!isOperator(tokens[i])) {
            double num = atof(tokens[i]);
            push(&stack, num);
        } 
        // 如果是运算符，弹出两个操作数进行计算
        else {
            double val2, val1;
            if (!pop(&stack, &val2) || !pop(&stack, &val1)) {
                printf("错误：表达式格式不正确\n");
                exit(EXIT_FAILURE);
            }
            double result = applyOp(val1, val2, tokens[i][0]);
            push(&stack, result);
        }
    }
    
    // 最终栈中应只剩一个元素，即计算结果
    double finalResult;
    if (!pop(&stack, &finalResult) || !isEmpty(&stack)) {
        printf("错误：表达式格式不正确\n");
        exit(EXIT_FAILURE);
    }
    return finalResult;
}

int main() {
    // 示例：计算 (3+4)*2/7
    char *tokens[] = {"3", "4", "+", "2", "*", "7", "/"};
    int tokenCount = sizeof(tokens) / sizeof(tokens[0]);
    
    printf("逆波兰表达式: ");
    for (int i = 0; i < tokenCount; i++) {
        printf("%s ", tokens[i]);
    }
    printf("\n");
    
    double result = evaluateRPN(tokens, tokenCount);
    printf("计算结果: %.2f\n", result);
    
    return 0;
}    