#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>  // 加入數學運算函數

#define N 50
#define OP 6

char op[OP] = {'(','+','-','*','/','^'};  // 增加 ^ 運算符
int op_priority[OP] = {0,1,1,2,2,3};     // 將 ^ 的優先級設為 3

int priority(char c);
void to_postfix(char infix[], char postfix[]);

char stack[N];  // This is a global variable.
int top = -1;

// -------------------------
//  將資料 item 放入堆疊
// -------------------------
void push(char item) {
    if (top >= N - 1) {
        printf("Stack full!\n");
        exit(-1);
    }
    stack[++top] = item;
}

// ------------------------------------ 
// 傳回堆疊頂端的資料，但並非取出  
// ------------------------------------ 
int pop() {
    if (top == -1) {
        printf("Stack empty!\n");
        exit(-1);
    }
    return stack[top--];
}

// ----------------------
// 判斷是否為空堆疊
// ----------------------
bool IsEmpty(void) {
    return (top < 0) ? true : false; 
}

// ----------------------
//  判斷堆疊是否滿溢
// ----------------------
bool IsFull() {
    return (top >= N - 1) ? true : false;
}

// --------------------------
// 傳回堆疊頂端的資料
// --------------------------
char top_data() {
    return stack[top]; 
}

// ---------------------------
// 傳回運算子 c 的優先序
// ---------------------------
int priority(char c) {
	int i;
    for (i = 0; i < OP; i++) {
        if (op[i] == c)
            return op_priority[i];
    }
    return -1;
}

// ------------------------------------
// 將中置式infix轉成後置式postfix
// ------------------------------------
void to_postfix(char infix[], char postfix[]) {
    int i = 0, j = -1;
    char x, y;

    while ((x = infix[i++]) != '\0') {
        if (x >= '0' && x <= '9') {
            // 處理多位數字
            while (infix[i] >= '0' && infix[i] <= '9') {
                postfix[++j] = x;
                x = infix[i++];
            }
            postfix[++j] = x;  // 將數字存入 postfix
            postfix[++j] = ' ';  // 用空格分隔數字
        } else {
            switch (x) {
                case '(':
                    push(x);
                    break;
                case ')':
                    while (!IsEmpty() && (y = pop()) != '(') {
                        postfix[++j] = y;
                        postfix[++j] = ' ';
                    }
                    break;
                case '+':
                case '-':
                case '*':
                case '/':
                case '^':
                    while (!IsEmpty() && priority(top_data()) > priority(x)) {
                        postfix[++j] = pop();
                        postfix[++j] = ' ';
                    }
                    push(x);
                    break;
                default:
                    break;
            }
        }
    }
    while (!IsEmpty()) {
        postfix[++j] = pop();
        postfix[++j] = ' ';
    }
    postfix[j] = '\0';
}

bool IsDigit(char c) {
    return c >= '0' && c <= '9';
}

int calculate(char postfix[]) {
    int point = 0, num = 0;
    while (postfix[point] != '\0') {
        if (IsDigit(postfix[point])) {
            num = 0;
            // 處理多位數字
            while (postfix[point] != ' ') {
                num = num * 10 + (postfix[point] - '0');
                point++;
            }
            push(num);  // 將數字壓入堆疊
        } else {
            if (postfix[point] != ' ') {
                int a = pop();
                int b = pop();
                int c = 0;
                switch (postfix[point]) {
                    case '+':
                        c = b + a;
                        break;
                    case '-':
                        c = b - a;
                        break;
                    case '*':
                        c = b * a;
                        break;
                    case '/':
                        c = b / a;
                        break;
                    case '^':
                        c = (int)pow(b, a);  // 指數運算
                        break;
                }
                push(c);
            }
        }
        point++;
    }
    return pop();  // 最後的結果
}

int main(void) {
    char infix[50], postfix[50];

    printf("請輸入運算式: ");
    scanf("%s", infix);
    to_postfix(infix, postfix);
    printf("\n中序式 : %s \t後序式 : %s\n", infix, postfix);
    printf("答案： %d\n", calculate(postfix));

    return 0;
}