魔兽世界附魔在哪附魔:把中缀表达式化为后缀表达式

来源:百度文库 编辑:九乡新闻网 时间:2024/03/28 20:10:38

//把中缀表达式化为后缀表达式
//基本解题思路
//使用栈的算法也很多,说个好想的。
//假设表达式的字符来自输入流in,建立栈A存放运算符,B存放结果,从in读入一个操作数压进B,读入一个运算符压进A,如此反复。
//1.读入一个元素e
//2.如果e是操作数或者(,压入B,跳转到1
//3.如果e是运算符(不包含括号),跳转到3.1
//4.如果e是),跳转到4.1
//5.如果e是EOF,即输入流结束,反复弹出A栈顶压入B,直到A为空,算法结束,B从栈底到栈顶的符号即为后缀表达式(需要把B翻个个儿^_^)

//3.1.判断A的栈定符号t,如果t不为(,且优先级大于等于e,则弹出t压入B,跳转到4,如果t为空,即栈中为空,或其他情况直接把e压入A,跳转到1
//4.1.弹出A的栈顶压入到B,如此反复直到弹出的符号为(,(和)不要压入B,跳转到1

#i nclude
#i nclude
#define MAX 100
typedef struct         //存放结果
{
 char data[MAX];
 int top;
}Stack1;
typedef struct         //存放符号
{
 char data[MAX];
 int top;
}Stack2;


//对栈进行初始化
void Init_Stack(Stack1 *SS1,Stack2 *SS2)
{
 SS1->top=SS2->top=-1;
 //SS1->data[SS1->top]=SS2->data[SS2->top]=0;
}


//判断+ - * /
int Jadge(char ch,Stack1 *SS1,Stack2 *SS2)
{
 int i;
 switch(ch)
 {
    case ‘+‘:  //对‘+‘号的处理
       if(SS1->data[SS1->top]==‘-‘||SS1->data[SS1->top]==‘*‘||SS1->data[SS1->top]==‘/‘)
    {  
     SS2->data[++SS2->top]=SS1->data[SS1->top--];
     SS1->data[++SS1->top]=ch;
  }
    else
     SS1->data[++SS1->top]=ch;
    return 1;
       /////////////////////////////
    case ‘-‘: //对‘-‘号的处理
    if(SS1->data[SS1->top]==‘+‘||SS1->data[SS1->top]==‘*‘||SS1->data[SS1->top]==‘/‘)
  {
     SS2->data[++SS2->top]=SS1->data[SS1->top--];
     SS1->data[++SS1->top]=ch;
  }

    else
     SS1->data[++SS1->top]=ch;
    return 1;
    /////////////////////////////

    case ‘*‘:  //对‘*‘的处理
    if(SS1->data[SS1->top]==‘/‘)  
  {
     SS2->data[++SS2->top]=SS1->data[SS1->top--];
     SS1->data[++SS1->top]=ch;
     }
        else
   SS1->data[++SS1->top]=ch; 
  return 1;

    ////////////////////////////

    case ‘/‘:  //对‘/‘的处理
    if(SS1->data[SS1->top]==‘*‘) 
  {
     SS2->data[++SS2->top]=SS1->data[SS1->top--];
     SS1->data[++SS1->top]=ch;
     }
        else
   SS1->data[++SS1->top]=ch;
     return 1;

    /////////////////////////////
     case ‘)‘:   //对‘)‘的处理
  i=SS1->top;

  //判断栈SS1中是否有与‘)‘匹配的‘(‘
  while(SS1->data[i]!=‘(‘ && i>=0)i--;
   if(i==-1)return 0;

        //遇到当‘)‘遇到‘(‘的操作
  while(SS1->data[SS1->top]!=‘(‘)
  {
   SS2->data[++SS2->top]=SS1->data[SS1->top--];
  }
  SS1->top--;
   
  return 1;
  //break;
       //3+4/(5-(6*5))*8
 }
}

void main()
{

 
 Stack1 *SS1=(Stack1 *)malloc(sizeof(Stack1));
 Stack2 *SS2=(Stack2 *)malloc(sizeof(Stack2));
 Init_Stack(SS1,SS2);
 //printf("%d %d",SS1->data[SS1->top],SS2->data[SS2->top]);
 int i,flag,k=0,sum1,sum2;
 char ch[MAX];
 printf("请输入中缀表达式:");
 gets(ch);
 while(ch[k])
 {
  // printf("%c ",*(ch+i));
   //i++;
  if(ch[k]>=‘0‘&&ch[k]<=‘9‘)
   SS2->data[++SS2->top]=ch[k];
  else if(ch[k]==‘(‘)
   SS1->data[++SS1->top]=ch[k];
  else if(ch[k]==‘+‘ ||ch[k]==‘-‘||ch[k]==‘*‘ || ch[k]==‘/‘||ch[k]==‘)‘)
   flag=Jadge(ch[k],SS1,SS2);
   if(!flag) break;
   k++;
 }
 if(flag)
 {
  //判断‘(‘与‘)‘的个数是否相同
  for(i=0;i<=SS1->top;i++)
  {
   if(ch[i]==‘(‘) sum1++;
   if(ch[i]==‘)‘) sum2++;
  }
  if(sum1!=sum2)
  {
   printf("表达式错误.\n");
   return;
  }
  //输出后缀表达式
  printf("后缀表达式为:");
  for(i=0;i<=SS2->top;i++)
   printf("%c ",SS2->data[i]);
  for(i=SS1->top;i>=0;i--)
   printf("%c ",SS1->data[i]);
  printf("\n");
 }

 else
  printf("表达式错误.\n");

 
}