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

//运算符栈
typedef struct node
{
    char data;
    struct node *next;
}LinkStackNode, *LinkStack;
//运算数栈
typedef struct Node
{
    int data;
    struct Node *next;
}LinkNode,*Link;

//初始化
void InitStack_op(LinkStack *top)
{
    *top = (LinkStack)malloc(sizeof(LinkStackNode));
    (*top)->next = NULL;
}
void InitStack_ov(Link *top)
{
    *top = (Link)malloc(sizeof(LinkNode));
    (*top)->next = NULL;
}
// 进栈
int Push_op(LinkStack top,char x)
{
    LinkStackNode * temp;
    temp = (LinkStackNode *)malloc(sizeof(LinkStackNode));
    if(temp == NULL)
        return 0;
    temp->data = x;
    temp->next = top->next;
    top->next = temp;
    return 1;
}

int Push_ov(Link top,int x)
{
    LinkNode *temp;
    temp = (LinkNode *)malloc(sizeof(LinkNode));
    if(temp == NULL)
        return 0;
    temp->data = x;
    temp->next = top->next;
    top->next = temp;
    return 1;
}
//出栈
int Pop_op(LinkStack top, char *x)
{
    LinkStackNode * temp;
    temp = top->next;
    if(temp == NULL)
        return 0;
    top->next = temp->next;
    *x = temp->data;
    free(temp);
    return 1;
}
int Pop_ov(Link top, int *x)
{
    LinkNode * temp;
    temp = top->next;
    if(temp ==NULL)
        return 0;
    top->next = temp->next;
    *x = temp->data;
    free(temp);
    return 1;
}
//判断输入字符是否为运算符
int In(char x)
{
    if(x == '+' || x == '-' || x == '*' || x == '/' || x == '#' || x == '(' || x ==')')
        return 1;
    return 0;
}
//获取栈顶元素
char GetTop_op(LinkStack top)
{
    return top->next->data;
}
int GetTop_ov(Link top)
{
    return top->next->data;
}
//运算操作
int Execute(int a, char op,int b)
{
    int i = 0;
    switch(op)
    {
    case '+':
        i = a + b;
        break;
    case '-':
        i = a - b;
        break;
    case '*':
        i = a * b;
        break;
    case '/':
        if(b == 0)
        {
            printf("错误，除数不能为0!\n");
            break;
        }
        i = a / b;
    default:
        break;
    }
    return i;
}
//字符转化为数字
int GetNumber(char &ch)
{
    return atoi(&ch);
}
//比较栈顶运算符的优先级

char Compare(char s,char c)
{
    switch(s)
    {
    case '+':
    case '-':
        {
            if(c=='+'||c=='-')
                return '>';
            else if (c=='*'||c=='/')
                return '<';
            else if(c=='(')
                return '<';
            else if(c==')')
                return '>';
            else
                return '>';
        }
        break;
    case '*':
    case '/':
        {
            if(c=='+'||c=='-')
                return '>';
            else if (c=='*'||c=='/')
                return '>';
            else if(c=='(')
                return '<';
            else if(c==')')
                return '>';
            else
                return '>';
        }
        break;
    case '(':
        {
            if(c==')')
                return '=';
            else
                return '<';
        }
        break;
    case ')':
        return '>';
        break;
    }
}

int main(void)
{
    LinkStack OPTR;
    Link OVS;
    InitStack_op(&OPTR);
    InitStack_ov(&OVS);
    char ch,op;
    int a,b,v,n;
    Push_op(OPTR,'#');
    printf("\n请输入一个表达式串(以 # 结尾):");
    ch = getchar();
    while(ch != '#' || GetTop_op(OPTR) != '#')
    {
        if(!In(ch))
        {
            n = GetNumber(ch);
            Push_ov(OVS,n);
        }
        else
            switch(Compare(GetTop_op(OPTR),ch))
        {
            case '<':
                Push_op(OPTR,ch);
                ch = getchar();
                break;
            case '>':
                Pop_ov(OVS, &b);
                Pop_ov(OVS, &a);
                Pop_op(OPTR,&op);
                v = Execute(a,op,b);
                Push_ov(OVS,v);
                break;
            case '=':
                Pop_ov(OVS, &b);
                Pop_ov(OVS, &a);
                Pop_op(OPTR,&op);
                v = Execute(a,op,b);
                Push_ov(OVS,v);
                break;
        }
    }
    v = GetTop_ov(OVS);
    printf("结果为:\n",v);
    return 0;
}