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

#define inf float(0x3f3f3f3f)
#define MAXSIZE 100

char priority[7] = {‘ ‘, ‘-‘, ‘*‘, ‘/‘, ‘(‘, ‘)‘, ‘#‘};

char priority_relationship[7][7] = {
    {‘>‘, ‘>‘, ‘<‘, ‘<‘, ‘<‘, ‘>‘, ‘>‘}, 
    {‘>‘, ‘>‘, ‘<‘, ‘<‘, ‘<‘, ‘>‘, ‘>‘}, 
    {‘>‘, ‘>‘, ‘>‘, ‘>‘, ‘<‘, ‘>‘, ‘>‘}, 
    {‘>‘, ‘>‘, ‘>‘, ‘>‘, ‘<‘, ‘>‘, ‘>‘}, 
    {‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘=‘, ‘ ‘}, 
    {‘>‘, ‘>‘, ‘>‘, ‘>‘, ‘ ‘, ‘>‘, ‘>‘}, 
    {‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘<‘, ‘ ‘, ‘=‘} 
};


typedef struct StackNode
{
    char data[MAXSIZE];   // 压入栈里面的数据都是字符型，在进行运行时，记得将字符型数字转换为整型数字
    struct StackNode *next;
}StackNode, *LinkStack;

void InitStack(LinkStack &S)
{// 构造一个空栈S，栈顶指针置空
    S = NULL;
}

void Push(LinkStack &S, char data[])
{// 在栈顶插入元素data
    StackNode *p;

    p = (StackNode *)malloc(sizeof(StackNode));  // 生成新的结点
    strcpy(p->data, data);  // 将新结点的数据域置为data
    p->next = S;    // 将新结点插入栈顶
    S = p;    // 修改栈顶指针为p
}

char *Pop(LinkStack &S)
{// 删除S的栈顶元素， 用data返回其值
    char data[MAXSIZE];
    if(S == NULL) printf("错误！！！n栈为空， 无法执行删除命令...");
    else
    {
        StackNode *p;

        strcpy(data, S->data);  // 将栈顶元素赋给data
        p = S;   // 用p临时保存栈顶元素的空间，以备释放
        S = S->next;   //修改栈顶指针 
        free(p);    // 释放原栈顶元素的空间
        return data;
    }
}

char *GetTop(LinkStack &S)
{
    if(S != NULL)
        return S->data;
    else
    {
        printf("错误！！！n栈顶为空");
        return "0";
    }
}

float str_to_float(char *str)
{
    float num = 0;
    int state_1 = 0;
    int state_2 = 0;
    while(( *str != ‘‘ && *str >= ‘0‘ && *str <= ‘9‘) || *str == ‘.‘ || (*str == ‘-‘ && *(str   1) != ‘‘))
    {
        if(*str == ‘.‘) state_1 = 1;
        else if(*str == ‘-‘) state_2 = 1;
        else
        {
            if(state_1 == 0) num = num * 10   (*str - ‘0‘);
            else
            {
                num  = (*str - ‘0‘) * pow(0.1, state_1);
                state_1  ;
            }
        }
        str  ;
    }
    if(*str != ‘‘) return inf;
    else if(state_2 == 1)
    {
        return num * -1;
    }
    else return num;
}

char *float_to_str(float num)
{
    char str[MAXSIZE];
    sprintf(str, "%.4f", num);  // 保留小数点后4位
    return str;
}

int get_index(char str[])
{
    for(int i = 0; i < 7; i  )
    {
        if(str[0] == priority[i]) return i;
    }
    printf("未找到匹配的字符n");
}

char Precede(char inside_data[], char input_data[])
{
    int inside_index = get_index(inside_data);
    int input_index = get_index(input_data);

    return priority_relationship[inside_index][input_index];
}

float Operate(char a[], char theta[], char b[])
{//执行运算
    float a_num = str_to_float(a);
    float b_num = str_to_float(b);

    if(theta[0] == ‘ ‘) return a_num   b_num;
    else if(theta[0] == ‘-‘) return a_num - b_num;
    else if(theta[0] == ‘*‘) return a_num * b_num;
    else if(theta[0] == ‘/‘) return a_num / b_num;
    else printf("错误！！！n无该运算符");
}

float EvaluateExpression()
{
    StackNode *OPND, *OPTR;
    char str[MAXSIZE];
    char theta[MAXSIZE];
    char a[MAXSIZE];
    char b[MAXSIZE];

    InitStack(OPND);
    InitStack(OPTR);
    Push(OPTR, "#");

    scanf("%s", str);
    while(str[0] != ‘#‘ || GetTop(OPTR)[0] != ‘#‘)
    {
        if(str_to_float(str) != inf)
        {
            Push(OPND, str);
            scanf("%s", str);
        }
        else
        {
            switch (Precede(GetTop(OPTR), str))
            {
            case ‘<‘:
                Push(OPTR, str);
                scanf("%s", str);
                break;
            case ‘>‘:
                strcpy(theta, Pop(OPTR));
                strcpy(b, Pop(OPND));
                strcpy(a, Pop(OPND));
                char temp_str[MAXSIZE];
                strcpy(temp_str, float_to_str(Operate(a, theta, b)));
                Push(OPND, temp_str);
                break;
            case ‘=‘:
                Pop(OPTR);
                scanf("%s", str);
                break;
            default:
                printf("错误！！！n该优先级不存在！！！");
            }
        }

    }

    return str_to_float(GetTop(OPND));
}

int main(void)
{
    float num;

    num = EvaluateExpression();
    printf("%fn", num);

    printf("n");
    system("pause");
}