#include"stdio.h"
#include"malloc.h"
#include"stdlib.h"
#include"string.h"
#define MAXSIZE 100

/*建立运算符栈*/
typedef struct
{
  char data[MAXSIZE];
  char top;
  char base;
}MyStack;

/*以下为函数声明*/
void Transform();
int In(char);
char Proceed(char ,char );

MyStack Stack;

/*初始化栈*/
void InitStack(MyStack*s)
{
 s->top=0;
 s->base=0;
}

/*判断栈是否为空*/
int Empty(MyStack*s)
{
 if(s->top==s->base)
 return 1;
 else
 return 0;
}

/*进栈*/
void Push(MyStack*s,char x)
{
 if(s->top==MAXSIZE)
 {
  printf("OVER FLOW!\n");
  exit(0);
 }
 else
 {
  s->data[s->top]=x;
  s->top++;
 }
}

/*出栈*/
char Pop(MyStack*s)
{
 char e;
 if(Empty(s))
 {
  printf("UNDER FLOW!/n");
  exit(0);
 }
 else
 {
  s->top--;
  e=s->data[s->top];
  return e;
 }
}

/*取栈顶*/
char GetTop(MyStack*s)
{
 if(Empty(s))
 {
  printf("UNDER FLOW!/n");
  exit(0);
 }
}

void Transform(char c[100],char temps[100])
{
 int i=0,j=0;
 char ch;
 InitStack(&Stack);
 Push(&Stack,'#');
 while(c[i]!='#' || GetTop(&Stack)!='#')
 {
    if(!In(c[i]))
    {
      if(c[i]>='0'&&c[i]<='9')
      {
         ch=c[i];
         temps[j]=ch;
         i++;
         j++;

          while(!In(c[i]))
           {
              if(c[i] >= '0' && c[i] <= '9'||c[i]=='.')
               {
                 ch=c[i];
                 temps[j]=ch;
                 i++;
                 j++;

               }
              else
               {
                 printf("The expression you input is wrong!\n");
                  exit(0);
               }
            }
         temps[j]=' ';
         j++;
       }
       else
        {
           printf("The expression you input is wrong!\n");
            exit(0);
        }

    }
    else switch(Proceed(GetTop(&Stack),c[i]))
    {
      case'<':
      Push(&Stack,c[i]);
      i++;
      break;

      case'=':
      Pop(&Stack);
      i++;
      break;

      case'>':
      ch=Pop(&Stack);
      temps[j]=ch;
      i++;
      j++;
      break;

    }
 }


}

int In(char c)
{
 char ch[7]={'+','-','*','/','#','(',')'};
    int i;
 for(i = 0; i < 7; i++)
  if(c == ch[i])
   return 1;
            return 0;            
}

char Proceed(char op,char c)
 {
   char ch;
   if(op=='('&&c==')'||op=='#'&&c=='#')
   ch='=';
   else if(op=='+'||op=='-')
   switch(c)
   {
    case'+':
    case'-':
    case')':
    case'#':ch='>';
    break;
    case'*':
    case'/':
    case'%':
    case'(':ch='<';
   }
   else if(op=='*'||op=='/'||op=='%')
    switch(c)
    {
      case'+':
      case'-':
      case'*':
      case'/':
      case'%':
      case')':
      case'#':ch='>';
      break;
      case'(':ch='<';
    }
    else if(op=='(')
    switch(c)
    {
     case'+':
     case'-':
     case'*':
     case'/':
     case'%':
     case'(':ch='<';
     break;
     case'#':printf("Error!\n");
     exit(0);
    }
    else if(op==')')     /*栈顶元素为‘)’*/
    switch(c)
    {
      case '+':
      case '-':
      case '*':
      case '/':
      case '%':
      case '#': ch = '>';
      break;
      case '(': printf("Error!\n"); exit(0);
    }
    else if(op=='#')
    switch(c)
    {
     case '+':
     case '-':
     case '*':
     case '/':
     case '%':
     case '(': ch = '<'; break;
     case ')':   printf("Error!\n");
     exit(0);
    }
   return ch;
 }


void main()
{

  char str[100],exp[100];
  printf("please input a expression and to be end with'#':");
  gets(str);

  Transform(str,exp);
  printf("The back_expression is:%s",exp);
  getch();
}