#include "stdio.h"
#include "stdlib.h"
#include "conio.h"
#include<iostream.h>
#define NULL 0

/*栈节点类型*/
typedef struct node
{
  char data;
  struct node *next;
 }snode,*slink;
  typedef struct node_post
 {   
  int data;
  struct node_post *next;
 }pnode,*plink;

/*全局变量定义*/
slink top=NULL;
plink ptop=NULL;

/*栈空检测，空时为1*/
int Emptystack()
{
  if(top==NULL)return 1;
  else return 0;
}

/*出栈，返回top中data*/
char Pop()
{
  char e;
  slink p;
  if(top==NULL)return(-1);
  else
  {
    p=top;
    top=top->next;
    e=p->data;
    free(p);
    return e;
  }
}
int Pop_post()
{
  int e;
  plink p;
  if(ptop==NULL)return(-1);
  else
  {
    p=ptop;
    ptop=ptop->next;
    e=p->data;
    //free(p);
    return e;
  }
}
char Gettop()//读栈
{
  char e;
  slink p;
  if(top==NULL)return(-1);
  else
  {
    p=top;
   // top=top->next;
    e=p->data;
    free(p);
    return e;
  }
}

/*进栈*/
void Push(char e)
{
  slink p;
  p=(slink)malloc(sizeof(snode));
  p->data=e;
  p->next=top;
  top=p;
 }
void Push_post(int e)
{
  plink p;
  p=(plink)malloc(sizeof(pnode));
  p->data=e;
  p->next=ptop;
  ptop=p;
}
int  Precede(char a1,char a2)
{
    int m,n;
    char b[8][8]={
    '0','+','-','*','/','(',')','#',
    '+','>','>','<','<','<','>','>',
    '-','>','>','<','<','<','>','>',
    '*','>','>','>','>','<','>','>',
    '/','>','>','>','>','<','>','>',
    '(','<','<','<','<','<','=','x',
    ')','>','>','>','>','x','>','>',
    '#','<','<','<','<','<','x','='};
    for(int i=1;i<=7;i++)
    {
        if(a1==b[0][i])
            m=i;
        if(a2==b[i][0])
            n=i;
    }
    if(b[m][n]=='>')
        return 1;
    else
        return 0;
}

/*中后续转换*/
void mid_post(char mid[],char post[])
{
  int i=0,j=0;
  char c;
  Push('#');
  do
  { c=mid[i++];
    switch(c)
  {
    case '#':
    {
       while(!Emptystack())
        post[j++]=Pop();
    }break;
    case ')':
    { while(Gettop()!='(')
      post[j++]=Pop();
      Pop();
    }break;
    case '+':
    case '-':
    case '*':
    case '/':
    case '(':
    { while(Precede(Gettop(),c))
      post[j++]=Pop();
      Push(c);
    }break;
    default:post[j++]=c;
    }
  }while(c!='#');

}

/*后缀表达式求值*/
void Postcount(char post[])
{ int i=0;
  char x,a,b;
  int z;
  while(post[i]!='#')
  { x=post[i];
    switch(x)
  {
  case '+':b=Pop_post();a=Pop_post();z=a+b;Push_post(z);break;
  case '-':b=Pop_post();a=Pop_post();z=a-b;Push_post(z);break;
  case '*':b=Pop_post();a=Pop_post();z=a*b;Push_post(z);break;
  case '/':b=Pop_post();a=Pop_post();z=a/b;Push_post(z);break;
  default:z=atoi(&x);Push_post(z);
  }
  i++;
  }
  if(ptop!=NULL)printf("The result is: %d",ptop->data);
  else printf("Failure");
}

void main()
{
  char post[255]=" ",mid[255]=" ";
  int j=1;
  do
  {
    printf("please enter expression(\"#\" as end):\n");
    scanf("%s",mid);
    printf("the expression eaual:\n");
    mid_post(mid,post);
    printf("%s\n",post);
    Postcount(post);
    cout<<"input 1 go on!\n input 0 exit!\n";
    cin>>j;
  }while(j);
}