#include <conio.h>
#include <string.h>
#include <stdio.h>
#include <ctype.h>
#include <alloc.h>

struct stake1
{ char *s[15];
  int top;
} chstake;/*運算元素棧*/

struct stake2
{ char ch[20];
  int sjb[20];
  int top;
} ysstake;/*運算符號棧*/

struct lgstake1
{ char ch[10];
  int top;
}logfh;/*邏輯運算符號棧*/

struct lgstake2
{ int ysbh[10];
  int top;
}logys;/*邏輯運算元素*/

struct syshi/*四元式隊列*/
{ char *s[4];
  int bhao;
  struct syshi *next;
}yshead,*ystail;/*頭節點和尾指針*/

int sysnum,bh,logopr;/*四元式個數和臨時變量個數*/
int truelink,falselink,tchuko;

void pushys(char *stemp) /*運算元素進棧*/
{ int ln;
  ln=strlen(stemp);
  chstake.s[chstake.top]=(char *)malloc((ln+1)*sizeof(char));
  strcpy(chstake.s[chstake.top],stemp);
  chstake.top++;
}

void pushsf(char ch1,int jb)/*運算符進棧*/
{ ysstake.ch[ysstake.top]=ch1;
  ysstake.sjb[ysstake.top]=jb;
  ysstake.top++;
}

char *popys() /*運算元素出棧*/
{ char *tp;
  chstake.top--;
  tp=chstake.s[chstake.top];
  chstake.s[chstake.top]=NULL;
  return(tp);
}

char popsf() /*運算符出棧*/
{ char ctemp;
  ysstake.top--;
  ctemp=ysstake.ch[ysstake.top];
  return(ctemp);
}

void back(int t1,int t2)
{ struct syshi *temp3;
  int bh3,t0;
  bh3=t1;
  while(bh3!=0)
  { temp3=yshead.next;
    while(temp3->bhao!=bh3) temp3=temp3->next;
    sscanf(temp3->s[0],"%d",&bh3);
    sprintf(temp3->s[0],"%d",t2);
  }
}

void batch()
{ struct syshi *temp1,*temp2,*temp3;
  int bh1,bh2,bh3,i=0;
  char ch1;
  while(i<logfh.top)
  { bh1=logys.ysbh[i];
    temp1=yshead.next;
    while(temp1->bhao!=bh1) temp1=temp1->next;
    ch1=logfh.ch[i];
    if(ch1=='&')
    { bh3=truelink;
      truelink=0;
      back(bh3,bh1+2);
      sprintf(temp1->s[0],"%d",bh1+2);
      temp1=temp1->next;
      sprintf(temp1->s[0],"%d",falselink);
      falselink=bh1+1;
    }
    if(ch1=='|')
    { sprintf(temp1->s[0],"%d",truelink);
      truelink=bh1;
      temp1=temp1->next;
      bh3=falselink;
      falselink=0;
      back(bh3,bh1+2);
      sprintf(temp1->s[0],"%d",bh1+2);
    }
    i++;
  }
  temp2=yshead.next;
  bh2=logys.ysbh[logys.top-1];
  while(temp2->bhao!=bh2) temp2=temp2->next;
  sprintf(temp2->s[0],"%d",truelink);truelink=bh2;
  temp2=temp2->next;
  sprintf(temp2->s[0],"%d",falselink);falselink=bh2+1;
  logys.top=0;
}

void logysh()
{ struct syshi *temp;
  temp=ystail;
  temp->next=(struct syshi *)malloc(sizeof(struct syshi));
  temp=temp->next;
  temp->bhao=100+bh;
  logys.ysbh[logys.top++]=100+bh;
  bh++;
  temp->s[0]=(char *)malloc(8*sizeof(char));
  strcpy(temp->s[0],"----");
  temp->s[1]=(char *)malloc(2*sizeof(char));
  strcpy(temp->s[1]," ");
  temp->s[2]=(char *)malloc(8*sizeof(char));
  sprintf(temp->s[2],"if %s goto",popys());
  temp->s[3]=(char *)malloc(2*sizeof(char));
  strcpy(temp->s[3]," ");
  temp->next=(struct syshi *)malloc(sizeof(struct syshi));
  temp=temp->next;
  temp->bhao=100+bh;bh++;
  temp->s[0]=(char *)malloc(8*sizeof(char));
  strcpy(temp->s[0],"----");
  temp->s[1]=(char *)malloc(2*sizeof(char));
  strcpy(temp->s[1]," ");
  temp->s[2]=(char *)malloc(8*sizeof(char));
  strcpy(temp->s[2],"goto");
  temp->s[3]=(char *)malloc(2*sizeof(char));
  strcpy(temp->s[3]," ");
  temp->next=NULL;
  ystail=temp;
}

void yunsuan()/*產生四元式*/
{ struct syshi *temp;
  int i,j;
  char ch,ctmp[2];
  ch=popsf();
  temp=(struct syshi *)malloc(sizeof(struct syshi));
  temp->s[1]=popys();
  temp->s[0]=popys();
  temp->s[2]=(char *)malloc(8*sizeof(char));
  temp->s[2][0]=ch;temp->s[2][1]='\0';
  temp->s[3]=(char *)malloc(8*sizeof(char));
  sprintf(temp->s[3],"t%d",sysnum++);
  temp->bhao=100+bh;
  bh++;
  ystail->next=temp;
  pushys(temp->s[3]);
  temp->next=NULL;
  ystail=temp;
  if(ch=='<'||ch=='>')
  logysh();
}

int fys(char ch) /*判斷運算符級別*/
{ int jb;
  switch(ch)
  { case '^': jb=5; break;
    case '*': jb=4; break;
    case '/': jb=4; break;
    case '+': jb=3; break;
    case '-': jb=3; break;
    case '<': jb=2; break;
    case '>': jb=2; break;
    case '=': jb=1; break;
    default: jb=0;
  }
  return(jb);
}

int count;

int cffx(char *s1)
{ int len=0,length,i,judge=1,logic=0;
  int flag=0,sfjb,qt=0;/*qt代表括號嵌套層數*/
  char ch,temp[20];
  length=strlen(s1);
  ch=s1[0];
  if(ch=='-')
  { pushys(" ");
    pushsf('-',3);
    ch=s1[++len];
  }
  while(len<length&&(judge==1))
  { if(isalpha(ch))/*是字母*/
    { if(flag==1) judge=-1;
      else
      { i=0;
        while((isalpha(ch)||isdigit(ch))&&(len<length))
        { temp[i]=ch;
          ch=s1[++len];
          i++;
        }
        temp[i]='\0'; flag=1;
        pushys(temp);
      }
    }/*取表達式中的字符變量*/
    else if(isdigit(ch))/*是數字*/
    { if(flag==1) judge=-1;
      else
      { i=0;
        while(isdigit(ch)&&(len<length))
        { temp[i]=ch;
          ch=s1[++len];
          i++;
        }
        if(ch=='.')
        { temp[i++]=ch;ch=s1[++len];
          while(isdigit(ch)&&(len<length))
          { temp[i]=ch;
            ch=s1[++len];
            i++;
          }
        }/*是小數取小數部分*/
        temp[i]='\0';
        flag=1;
        pushys(temp);
      }
    }/*取表達式中的數字常量*/
    else if(ch=='(')
    { if(flag==1) judge=-1;
      else
      { pushsf('#',-100);/*符號棧進棧一個間隔*/
        i=0; ch=s1[++len];
        while((ch!=')'&&len<length)||qt>0)
        { if(ch==')') qt--;
          if(ch=='(')
          { qt++;
            count++;
          }
          temp[i]=ch;
          ch=s1[++len];
          i++;
        }
        if(ch!=')') judge=-2;/*括號不匹配*/
        else
        { temp[i]='\0';
          judge=cffx(temp);
          ch=s1[++len];
          flag=1;
          popsf();
        }
      }
    }/*處理表達式中的括號 */
    else if(ch=='&'||ch=='|')
    { if(flag==0)
      judge=-3;
      else
      { flag=0;
        logic=1;
        logfh.ch[logfh.top]=ch;
        logfh.top++;
        ch=s1[++len];
        logopr++;
      }
    }
    else
    { if(flag==0) judge=-3;/*運算符相連錯誤*/
      else
      { flag=0;
        sfjb=fys(ch);
        if(sfjb==2&&logopr>0) logopr--;
        if(sfjb==0) judge=-4;/*出現非法運算符    */
        else
        { while(sfjb<=ysstake.sjb[ysstake.top-1])/*該運算符優先級小 */
          yunsuan();/*運算產生四元式*/
          pushsf(ch,sfjb);
          ch=s1[++len];
        }
      }
    }/*運算符處理 */
  }
  while(judge==1&&(ysstake.top!=1)&&(ysstake.ch[ysstake.top-1]!='#'))
  yunsuan();
  if(logopr!=0&&(count==0))
  { logysh();
    logopr--;
  }
  if(logic&&judge==1)
  { batch();
    printf("FALSE :%4d TRUE :%4d\n",falselink,truelink);
  }
  if(count>0) count--;
  return(judge);
}


void display()
{ struct syshi *temp;
  temp=yshead.next;
  while(temp)
  { printf("%-4d %-6s %-6s %-6s %-6s\n",
    temp->bhao,temp->s[2],temp->s[0],temp->s[1],temp->s[3]);
    temp=temp->next;
  }
}

void htian()
{ struct syshi *temp;
  int tbh,bh1;
  tbh=truelink;
  while(tbh!=0)
  { temp=yshead.next;
    while(temp->bhao!=tbh) temp=temp->next;
    sscanf(temp->s[0],"%d", &tbh);
    sprintf(temp->s[0],"%d",tchuko+100);
  }
  tbh=falselink;
  while(tbh!=0)
  { temp=yshead.next;
    while(temp->bhao!=tbh) temp=temp->next;
    sscanf(temp->s[0],"%d", &tbh);
    sprintf(temp->s[0],"%d",bh+100);
   }
}

void inigtial()
{ int i;
  sysnum=0;bh=0;
  truelink=0;falselink=0;
  chstake.top=0;
  for(i=0;i<15;i++)
    chstake.s[i]=NULL;
  ysstake.top=1;
  ysstake.sjb[0]=0;
  for(i=0;i<3;i++)
    yshead.s[i]=NULL;
  yshead.next=NULL;
  ystail=&yshead;
  logfh.top=0;
  logys.top=0;
  logopr=0;
  count=0;
}

void main(){
 int i,test,control;
 char ss[20],ss2[20];
 clrscr();
 printf("CHOOSE (0)EXIT (1)TRANSLATE:");
 scanf("%d",&control);
 while(control){
   inigtial();
   printf("Input The Arithmetic Formula:");
   scanf("%s",ss);
   if(ss[0]=='i'&&ss[1]=='f'&&ss[2]=='('){
      count--;
      test=cffx(&ss[2]);
      tchuko=bh;
      scanf("%s",ss2);
      test=cffx(ss2);
   }
   else{
      test=cffx(ss);
   }
   if(test>0){
      if(logys.top!=0){
         batch();
         printf("FALSE :%4d TRUE :%4d\n",falselink,truelink);
      }
      display();
      if(truelink!=0&&ss[0]=='i'){
         printf("*****press any key to backfill*****\n");
         getch();
         htian();
         display();
      }
   }
   else{
      printf("error expression!!");
      switch(test){
         case -1: printf("error const or var!");break;
         case -2: printf("error blacket!");break;
         case -3: printf("error functor!");break;
         case -4: printf("error char!");break;
      }
   }
   getch();
   clrscr();
   printf("CHOOSE (0)EXIT (1)TRANSLATE");
   scanf("%d",&control);
 }
}