#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <math.h>
#include "mystack.h"
#include "myqueue.h"

#define DEBUG               0
#define MAX_LENGTH_TXT      500

typedef enum {
    ERR_NONE = 0,
    ERR_IO,
    ERR_STACK,
    ERR_QUEUE
} errNum;

typedef struct {
    errNum error;
    int line;
} myError;

int getExpr(char expr[]);
myError processQueue(char expr[], int len_txt);
double calcQueue();
char* zeroRid(double num);

int main() {
    char expr[MAX_LENGTH_TXT];
    int len_txt = 0;
    myError err;
    double res;

    while (1) {
        stackClean();
        queueClean();
        printf("please input a expression (Supported operators '+ - * / ( )' and Bracket nesting) or 'q' to exit\n> ");
        len_txt = getExpr(expr);                // 获取输入
        if (len_txt == -1) {
            break;
        } else if (len_txt == 0) {
            continue;
        }
#if (DEBUG == 1)
        printf("> %s | Length: %d\n", expr, len_txt);
#endif
        err = processQueue(expr, len_txt);      // 处理表达式
        if (err.error == ERR_IO) {
            printf("[ERROR_IO]: (Line: %d)Please check the input carefully and try again later\n", err.line);
            continue;
        } else if (err.error == ERR_QUEUE) {
            printf("[ERROR_QUEUE]: (Line: %d)Queue full, input too long please try again\n", err.line);
            continue;
        } else if (err.error == ERR_STACK) {
            printf("[ERROR_STACK]: (Line: %d)Stack full, input too long please try again\n", err.line);
            continue;
        }
#if (DEBUG == 1)
        printf("> ");
        queuePrint();
#endif
        res = calcQueue();                      // 计算结果
        printf("= %s\n", zeroRid(res));
    }

    return 0;
}

/* 获取运算符优先级 */
uint8_t priority(char symbol) {
    switch (symbol) {
        case '+':
        case '-': return 1;
        case '*':
        case '/': return 2;
        case '(': return 3;
    }
    return 0;
}

/* 从标准输入中读入一行表达式 
 * 返回读入的字符串长度
 * -1 表示输入为退出标记或栈满退出
 */
int getExpr(char expr[]) {
    char ch;
    int len_txt = 0;
    while (1) {
        ch = getchar();
        if (ch == 'q') {  // 输入q， 直接退出
            len_txt = -1;
            break;
        }
        if ((ch >= '0' && ch <= '9') || ch == '.' || ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '(' || ch == ')') {
            /* 输入过滤 */
            expr[len_txt++] = ch;
            if (len_txt >= MAX_LENGTH_TXT) {
                len_txt = -1;  
                break;  // 输入溢出
            }
        } else if (ch == '\n') {
            expr[len_txt] = '\0';
            break;
        }
    }
    return len_txt;
}

/* 处理中序表达式，以逆波兰形式存入队列
 * 没有错误，返回0
 */
myError processQueue(char expr[], int len_txt) {
    int8_t  flag_sym_fr = 1;        // 标记数值正负，数值入队列后复位
    int8_t  flag_sym_bk[50] = {0},
            flag_sym_bk_cnt = 0;    // 标记左括号后缀，由右括号复位
    int8_t  flag_point = 1;         // 浮点数转换时标记位，数值入对列后复位
    char symbol;
    double value;
    myNode temp_node;
    uint8_t isok;
    myError t_err = {ERR_NONE};

    for (int i = 0; i < len_txt; ++i) {
        if (expr[i] == '+' || expr[i] == '-' || expr[i] == '*' || expr[i] == '/') {
            /* 加减乘除符号处理 */
            if (expr[i] == '+' || expr[i] == '-') {
                /* 加减号处理 */
                if (i == 0 || expr[i-1] == '+' || expr[i-1] == '-' || expr[i-1] == '*' || expr[i-1] == '/' || expr[i-1] == '(') {
                    /* 正负作为数值前缀 */
                    if (expr[i] == '-') {  // 负号处理
                        if (expr[i+1] == '(') {  // 符号后是左括号
                            flag_sym_bk[flag_sym_bk_cnt] = 1;
                        } else if ((expr[i+1] >= '0' && expr[i+1] <= '9') || expr[i+1] == '.') {  // 符号后是数字或小数点
                            flag_sym_fr = -1;
                        } else {  // 错误输入
                            t_err.error = ERR_IO;
                            t_err.line = __LINE__;
                            break;  // 错误输入处理
                        }
                    } else {  // 正号处理
                        if (!((expr[i+1] >= '0' && expr[i+1] <= '9') || expr[i+1] == '.')) {  // 符号后不是数字或小数点
                            t_err.error = ERR_IO;
                            t_err.line = __LINE__;
                            break;  // 错误输入处理
                        }
                    }
                } else {
                    /* 正负作为运算符 */
                    isok = stackTop(&symbol);  // 获取栈顶符号
                    while (isok && symbol != '(' && priority(expr[i]) <= priority(symbol)) {
                        /*
                         *  字符优先级低于栈顶符号，依次弹栈直到遇到字符优先级高于栈顶符号或者遇到左括号或者空栈
                         *  (如果和栈顶符号优先级一样栈顶符号也要先弹栈，因为优先级一样运算顺序是从左往右)
                         */
                        temp_node.type = ENUM_SYMBOL;
                        stackPop(&temp_node.value.symbol);  // 弹栈
                        isok = queuePush(temp_node);  // 入队列
                        if (!isok) {
                            t_err.error = ERR_QUEUE;
                            t_err.line = __LINE__;
                            break;  // 队列满报错
                        }
                        isok = stackTop(&symbol);  // 重新获取栈顶符号
                    }
                    if (t_err.error != ERR_NONE) break;
                    isok = stackPush(expr[i]);  // 当前符号入栈
                    if (!isok) {
                        t_err.error = ERR_STACK;
                        t_err.line = __LINE__;
                        break;  // 栈满报错
                    }
                }
            } else {
                /* 乘除号处理 */
                if ((i == 0 && queueIsEmpty()) || expr[i+1] == '*' || expr[i+1] == '/' || expr[i+1] == ')') {
                    t_err.error = ERR_IO;
                    t_err.line = __LINE__;
                    break;  // 错误输入处理
                }
                isok = stackTop(&symbol);  // 获取栈顶符号
                while (isok && symbol != '(' && priority(expr[i]) <= priority(symbol)) {
                    /*
                     *  字符优先级低于栈顶符号，依次弹栈直到遇到字符优先级高于栈顶符号或者遇到左括号或者空栈
                     *  (如果和栈顶符号优先级一样栈顶符号也要先弹栈，因为优先级一样运算顺序是从左往右)
                     */
                    temp_node.type = ENUM_SYMBOL;
                    stackPop(&temp_node.value.symbol);  // 弹栈
                    isok = queuePush(temp_node);  // 入队列
                    if (!isok) {
                        t_err.error = ERR_QUEUE;
                        t_err.line = __LINE__;
                        break;  // 队列满报错
                    }
                    isok = stackTop(&symbol);  // 重新获取栈顶符号
                }
                if (t_err.error != ERR_NONE) break;
                isok = stackPush(expr[i]);  // 当前符号入栈
                if (!isok) {
                    t_err.error = ERR_STACK;
                    t_err.line = __LINE__;
                    break;  // 栈满报错
                }
            }
        } else if (expr[i] == '(') {
            /* 左括号直接入栈 */
            if (expr[i-1] == ')') {
                expr[i-1] = '*';
                i -= 2;
                continue;
            }
            if (flag_sym_bk[flag_sym_bk_cnt] || flag_sym_bk_cnt != 0) {
                flag_sym_bk_cnt++;
            }
            isok = stackPush(expr[i]);
            if (!isok) {
                t_err.error = ERR_STACK;
                t_err.line = __LINE__;
                break;  // 栈满报错
            }
        } else if (expr[i] == ')') {
            /* 右括号，依次弹栈入队列，直到遇到左括号 */
            do {
                isok = stackPop(&symbol);
                if (!isok) {
                    t_err.error = ERR_IO;
                    t_err.line = __LINE__;
                    break;  // 错误输入处理
                }
                if (symbol != '(') {
                    temp_node.type = ENUM_SYMBOL;
                    temp_node.value.symbol = symbol;
                    isok = queuePush(temp_node);  // 入队列
                    if (!isok) {
                        t_err.error = ERR_QUEUE;
                        t_err.line = __LINE__;
                        break;  // 队列满报错
                    }
                }
            } while (symbol != '(');
            if (t_err.error != ERR_NONE) break;
            /* 处理并复位标记 flag_sym_bk */
            if (flag_sym_bk_cnt && flag_sym_bk[--flag_sym_bk_cnt]) {
                temp_node.type = ENUM_SYMBOL;
                temp_node.value.symbol = '#';
                isok = queuePush(temp_node);  // 入队列
                if (!isok) {
                    t_err.error = ERR_QUEUE;
                    t_err.line = __LINE__;
                    break;  // 队列满报错
                }
                flag_sym_bk[flag_sym_bk_cnt] = 0;
            }
        } else {
            /* 读取数字并入队列 */
            if (i > 0 && expr[i-1] == ')') {
                expr[i-1] = '*';  // 数值前为右括号则用乘号填充
                i -= 2;
                continue;
            }
            value = 0.0;
            while ((expr[i+1] >= '0' && expr[i+1] <= '9') || expr[i+1] == '.') {
                if (expr[i] == '.') {
                    if (flag_point == 1) {
                        flag_point = -1;
                    } else {
                        t_err.error = ERR_IO;
                        t_err.line = __LINE__;
                        break;  // 错误输入处理
                    }
                } else {
                    if (flag_point == 1) {
                        value = value * 10 + (expr[i] - '0');
                    } else {
                        value = value + pow(10, flag_point--) * (expr[i] - '0');
                    }
                }
                ++i;
            }
            if (t_err.error != ERR_NONE) break;
            if (expr[i] == '.') {
                if (flag_point == 1) {
                    flag_point = -1;
                } else {
                    t_err.error = ERR_IO;
                    t_err.line = __LINE__;
                    break;  // 错误输入处理
                }
            } else {
                if (flag_point == 1) {
                    value = value * 10 + (expr[i] - '0');
                } else {
                    value = value + pow(10, flag_point--) * (expr[i] - '0');
                }
            }
            temp_node.type = ENUM_NUMBER;
            temp_node.value.number = value * flag_sym_fr;
            isok = queuePush(temp_node);  // 入队列
            if (!isok) {
                t_err.error = ERR_QUEUE;
                t_err.line = __LINE__;
                break;  // 队列满报错
            }
            /* 后续处理 */
            flag_sym_fr = 1;
            flag_point = 1;
            if (expr[i+1] == '(') {
                expr[i--] = '*';
            }
        }
    }
    if (t_err.error == ERR_NONE) {
        isok = stackPop(&symbol);
        while (isok) {
            if (symbol == '(') {
                /* 处理并复位标记 flag_sym_bk */
                if (flag_sym_bk_cnt && flag_sym_bk[--flag_sym_bk_cnt]) {
                    temp_node.type = ENUM_SYMBOL;
                    temp_node.value.symbol = '#';
                    isok = queuePush(temp_node);  // 入队列
                    if (!isok) {
                        t_err.error = ERR_QUEUE;
                        t_err.line = __LINE__;
                        break;  // 队列满报错
                    }
                    flag_sym_bk[flag_sym_bk_cnt] = 0;
                }
            } else {
                temp_node.type = ENUM_SYMBOL;
                temp_node.value.symbol = symbol;
                isok = queuePush(temp_node);  // 入队列
                if (!isok) {
                    t_err.error = ERR_QUEUE;
                    t_err.line = __LINE__;
                    break;  // 队列满报错
                }
            }
            isok = stackPop(&symbol);  // 重新获取栈顶符号
        }
    }
    return t_err;
}

double m_add(double a, double b) {
    return (a + b);
}

double m_sub(double a, double b) {
    return (a - b);
}

double m_mul(double a, double b) {
    return (a * b);
}

double m_div(double a, double b) {
    return (a / b);
}

double m_neg(double a) {
    return -a;
}

/* 根据逆波兰队列计算式值 */
double calcQueue() {
    double t_a, t_b, t_stack[MAX_LENGTH_QUEUE];
    int t_stack_cnt = 0;
    myNode t_node;
    uint8_t isok;

    isok = queuePop(&t_node);
    while (isok) {
        if (t_node.type == ENUM_NUMBER) {
            t_stack[t_stack_cnt++] = t_node.value.number;
        } else {
            switch (t_node.value.symbol) {
                case '+': {
                    t_b = t_stack[--t_stack_cnt];
                    t_a = t_stack[--t_stack_cnt];
                    t_stack[t_stack_cnt++] = m_add(t_a, t_b);
                    break;
                }
                case '-': {
                    t_b = t_stack[--t_stack_cnt];
                    t_a = t_stack[--t_stack_cnt];
                    t_stack[t_stack_cnt++] = m_sub(t_a, t_b);
                    break;
                }
                case '*': {
                    t_b = t_stack[--t_stack_cnt];
                    t_a = t_stack[--t_stack_cnt];
                    t_stack[t_stack_cnt++] = m_mul(t_a, t_b);
                    break;
                }
                case '/': {
                    t_b = t_stack[--t_stack_cnt];
                    t_a = t_stack[--t_stack_cnt];
                    t_stack[t_stack_cnt++] = m_div(t_a, t_b);
                    break;
                }
                case '#': {
                    t_a = t_stack[--t_stack_cnt];
                    t_stack[t_stack_cnt++] = m_neg(t_a);
                    break;
                }
            }
        }
        isok = queuePop(&t_node);
    }

    return t_stack[0];
}

/* 美化数值显示 */
char* zeroRid(double num) {
    static char str[200];
    char *point = str, *zero;

    sprintf(str, "%.15lf", num);
    while (*point != '.') point++;
    zero = str + 16;
    if (zero < point) {
        sprintf(str, "%g", num);
    } else {
        while (*zero == '0') zero--;
        if (*zero == '.') {
            *zero = '\0';
        } else {
            *(zero + 1) = '\0';
        }
    }
    
    return str;
}