5-3 jmu-符号配對 (15分)

#include <stdio.h>

 #include <stdlib.h>

 struct node

 {

     int data;

     struct node *next;

 };

 typedef struct node *stack;

 stack initStack()

 {

     stack s=(stack)malloc(sizeof(struct node));

     s->next=NULL;

     return s;

 }

 int isEmpty(stack s)

 {

     return s->next==NULL;

 }

 void push(stack s,int x)

 {

     stack p=(stack)malloc(sizeof(struct node));

     p->data=x;

     p->next=s->next;

     s->next=p;

 }

 void pop(stack s,int *x)

 {

     stack p=s->next;

     if(isEmpty(s))

     {

         printf("Stack is empty!\n");

         return;

     }

     s->next=p->next;

     *x=p->data;

     free(p);

 }

 int getTop(stack s)

 {

     return s->next->data;//傳回棧底的節點的data的值

 }







 int ExpCorrect(char exp[],int n)

 {

     int i;

     stack s=initStack();

     for(i=0; i<n; i++)

     {

         if(exp[i]=='('||exp[i]=='[')

             push(s,exp[i]);

         else if(exp[i]==')'||exp[i]==']')

         {

             int x;

             if(isEmpty(s))  return 0;

             pop(s,&x);

             if(exp[i]==')'&&x!='(')

                 return 0;

             if(exp[i]==']'&&x!='[')

                 return 0;

         }

     }

     if(isEmpty(s)) return 1;

     else return 0;

 }

 int Palindrome(char str[],int n)

 {

     char *p=str;

     stack s=initStack();

     for(; p<str+n/2; p++)

         push(s,*p);

     if(n%2)    p++;

     while(*p!='\0')

     {

         int x;

         pop(s,&x);

         if(x!=*p)

             return 0;

         p++;

     }

     return 1;

 }

 //判斷是否為運算符

 int isOper(char c)

 {

     switch(c)

     {

     case '+':

     case '-':

     case '*':

     case '/':

     case '(':

     case ')':

     case '#':

         return 1;

         break;//是運算符就傳回1

     default :

         return 0;//不是就傳回0

     }



 }





 //比較棧内和棧外的優先級c1内 c2外

 char compare(char c1,char c2)

 {

     //先定義兩個變量,用來表示優先級别

     int a,b;

     //對棧内的a進行複制

     switch(c1)

     {

     case '#':

         a=-1;

         break;

     case '(':

         a=0;

         break;

     case '+':

     case '-':

         a=2;

         break;

     case '*':

     case '/':

         a=4;

         break;

     }

     //對棧外的b進行複制

     switch(c2)

     {

     case '#':

         b=-1;

         break;

     case '(':

         b=5;

         break;

     case ')':

         b=0;

         break;

     case '+':

     case '-':

         b=1;

         break;

     case '*':

     case '/':

         b=3;

         break;

     }

     if(a>b)

     {

         return '>';

     }

     if(a==b)

     {

         return '=';

     }

     if(a<b)

     {

         return '<';

     }

 }



 //計算x op y的結果兩個操作數的結果

 int twoResult(char op,int x,int y)

 {

     int z;

     switch(op)

     {

     case '+':

         z=x+y;

         break;

     case '-':

         z=x-y;

         break;

     case '/':

         z=x/y;

         break;

     case '*':

         z=x*y;

         break;

     }

     return z;

 }



 //中綴表達式轉化為字尾表達式

 char *changeToback(char str[])

 {

     char *str2=(char *)malloc(sizeof(char)*100);

     stack s=initStack();

     int i=0,j=0,x;//中綴變字尾要兩個指向x用來存放出戰的資料元素

     push(s,'#');//先存入#作為之後的有關的判斷

     strcat(str,"#");//将#連結到原來的表達式中

     while(getTop(s)!='#'||str[i]!='#')

     {



         if(!isOper(str[i]))

         {

             str2[j++]=str[i++];

         }

         else

         {

             str2[j++]='?';

             switch(compare(getTop(s),str[i])) //求出棧頂内和棧外的進行比較

             {



             case '>':

                 pop(s,&x);

                 str2[j++]=x;

                 break;//出棧，儲存到str2這個數組之中

             case '=':

                 pop(s,&x);

                 i++;

                 break;//出棧不輸出

             case '<':

                 push(s,str[i++]);

                 break;//入棧

             }

         }

     }

     str2[j]='\0';

     return str2;

 }



 //字尾表達式求值

 int expressResult(char *p)

 {

     int sum=0,cot=0;

     char *q=p;

     int previous;

     int next;

     int count=0;

     stack s=initStack();//初始化棧對象

 //    while(*p!='\0')//當p指向的是一個'\0'的時候代表便利完成

 //    {

 //

 //        if(*p<=55&&*p>=48) //當指向的值不是符号的時侯将數字存入到棧記憶體中

 //        {

 //            //先盡行資料的類型轉化

 //            *p=*p-48;

 //            push(s,*p);

 //        }

 //        else

 //        {

 //            if(count==0)

 //            {

 //                pop(s,&next);

 //                sum=next;   //将第一個next的值指派給sum

 //                count++;

 //            }

 //            pop(s,&previous);

 //            sum=twoResult(*p,sum,previous);

 //        }

 //        p++;

 //

 //    }

 //    return sum;

     while(*p!='\0')

     {

         if(*p<=57&&*p>=48&&*p!='?') //當指向的值不是符号的時侯将數字存入到棧記憶體中

         {

             //先盡行資料的類型轉化

             cot=cot*10+(*p-48);//得到目前的資料

             q=p+1;//判斷下一個是否為？

             if(*q=='?')

             {

                 push(s,cot);

                 cot=0;//将cot重置為0，友善下一次存儲

             }

         }

         else if(*p!='?')

         {

 //            if(count==0)

 //            {

 //                pop(s,&next);

 //                sum=next;   //将第一個next的值指派給sum

 //                count++;

 //            }

 //            pop(s,&previous);

 //            sum=twoResult(*p,sum,previous);

             pop(s,&previous);

             pop(s,&next);

             sum=twoResult(*p,next,previous);

             push(s,sum);

         }

         p++;

     }

     sum=twoResult(*p,next,sum);

     return sum;

 }











 int main()

 {

     char str[100001];

 //    while(1)

 //    {

 //        gets(str);

 //        if(Palindrome(str,strlen(str)))

 //            puts("Yes!");

 //        else

 //            puts("No!");

 //    }

 //    int value;

 //    char str[100],*p,*cont;

 //    while(1)

 //    {

 //        gets(str);

 //        p=changeToback(str);

 //        cont=p;//這個指針用來便利，若直接使用p後面會抛出空指針異常

 //        for(; *cont!='\0'; cont++)

 //        {

 //            if(*cont=='?'||*cont=='#')

 //            {

 //                printf(" ");

 //                continue;

 //            }

 //            printf("%c",*cont);

 //        }

 //        printf("\n");

        puts(p);

 //        value=expressResult(p);

 //        printf("%d\n",value);

 //

 //    }

 gets(str);

 int len;

 len=strlen(str);

 if(ExpCorrect(str,len)){

     printf("yes");

 }else{

     printf("no");

 }

     return 0;

 }