消除左递归得到后缀式.c

解法:对原文法消除左递归,根据消除左递归后的等价文法建立语法树,而后对此语法树 进行后根遍历,即可得到后缀式.

/*
  给定文法G，产生式如下：（以S为开始符号）
  S -> I := E
  E -> E+T | E-T | T
  T -> T*F | T/F | T%F | F
  F -> (E) | I | -F
  I -> a|b|c|...|z
  编程，对任意输入w$($为结束符号)，若w属于L(G)则输出w的后缀式，否则输出
error.
*/
/*
    解法:对原文法消除左递归,根据消除左递归后的等价文法建立语法树,而后对此语法树
进行后根遍历,即可得到后缀式.

    消除左递归后,翻译模式如下 :
  S -> I := E  {S.node = make_node(":=",I.node,E.node)}
  E -> T   {R.in = T.node}
       R   {E.node = R.node}
  R -> +T  {R1.in = make_node('+',R.in,T.node)}
       R1  {R.node = R1.node}
  R -> -T  {R1.in = make_node('-',R.in,T.node)}
       R1  {R.node = R1.node}
  R -> ε  {R.node = R.in}
  T -> F   {P.in = F.node}
       P   {T.node = P.node}
  P -> *F  {P1.in = make_node('*',P.in,F.node)}
       P1  {P.node = P1.node}
  P -> /F  {P1.in = make_node('/',P.in,F.node)}
       P1  {P.node = P1.node}
  P -> %F  {P1.in = make_node('%',P.in,F.node)}
       P1  {P.node = P1.node}
  P -> ε  {P.node = P.in}
  F -> (E) {F.node = E.node}
  F -> I   {F.node = I.node}
  F -> -F  {F.node = make_node('-',NULL,F.node)}
  I -> a|b|...|z   {I.node = make_node(id,NULL,NULL)}
  根据以上翻译模式,即可写出程序.
*/
#include <malloc.h>
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>

typedef struct tagNode   /*语法树的结点结构*/
        {
          char value;
          struct tagNode *left_child;
          struct tagNode *right_child;
        } NODE;

char ch;  /*保存读入的字符*/

NODE *S(void);  /*以下各行为函数声明*/
NODE *I(void);
NODE *E(void);
NODE *R(NODE *);
NODE *T(void);
NODE *P(NODE *);
NODE *F(void);
void error(void);
void getnc(void);

/*建立结点.
  参数:
    value:新结点所带的字符
    left_child:左子树的指针
    right_child:右子树的指针
  返回:
    新建立的结点的指针
*/
NODE *make_node(char value,NODE *left_child,NODE *right_child)
{
  NODE *new_node = (NODE *)malloc(sizeof(NODE));
  new_node->left_child = left_child;
  new_node->right_child = right_child;
  new_node->value = value;
  return new_node;
}

/*错误处理.
  本函数将导致程序退出.
*/
void error()
{
  printf("\nerror.");
  exit(0);
}

/*后序遍历二叉树*/
void post_order_walk(NODE *root)
{
  if (root->left_child)
    post_order_walk(root->left_child);
  if (root->right_child)
    post_order_walk(root->right_child);
  /*这里用了一个小技巧:由于结点中的value字段为一char变量,不能表示多于一个字符
    的信息,如题目要求的赋值符 ":=". 我用等号代替 := ,但在遍历语法树时,如果碰
    到等号,就打印":="
  */
  if (root->value != '=')
    printf("%c ",root->value);
  else
    printf(":=");
}

/*取一字符,并略去空格和回车*/
void getnc()
{
  do
  {
    ch = getchar();
  }
  while (ch == ' ' || ch == '\n');
}

NODE *I()
{
  if (ch >= 'a' && ch <= 'z')
  {
    char result = ch;
    getnc();
    return make_node(result,NULL,NULL);
  }
  else
    error();
}

NODE *S()
{
  NODE *i_val = I();
  if (ch == ':')
  {
    /*由于":"和"="必需连在一起,这里不能调用上面的getnc(),而直接调用C语言
      函数库中的getchar()取得下一字符
    */
    ch = getchar();
    if (ch == '=')
    {
      getnc();
      return make_node('=',i_val,E());
    }
  }
  error();
}

NODE *E()
{
  return R(T());
}

NODE *R(NODE *r_in)
{
  if (ch == '+')
  {
    getnc();
    return R(make_node('+',r_in,T()));
  }
  else if (ch == '-')
  {
    getnc();
    return R(make_node('-',r_in,T()));
  }
  else
    return r_in;
}

NODE *T()
{
  return P(F());
}

NODE *P(NODE *p_in)
{
  if (ch == '*')
  {
    getnc();
    return P(make_node('*',p_in,F()));
  }
  else if (ch == '/')
  {
    getnc();
    return P(make_node('/',p_in,F()));
  }
  else if (ch == '%')
  {
    getnc();
    return P(make_node('%',p_in,F()));
  }
  else
    return p_in;
}

NODE *F()
{
  if (ch == '(')
  {
    NODE *result;
    getnc();
    result = E();
    if (ch != ')')
      error();
    getnc();
    return result;
  }
  else if (ch == '-')
  {
    /*一元运算符的结点根据老师上课的笔记,应该是左子女为NULL,右子女为运算对象.
      实际上最好不用"-"号作为一元运算符,因为这样容易引起混淆.如:
      b*d + c * -d 的后缀式为:b d * c d - * + 这里的"-"是一元运算符
      b*d*(c-d)    的后缀式为:b d * c d - *   这里的"-"是二元运算符
      考试时万一老师对此计较,应能说出道理.
    */
    getnc();
    return make_node('-',NULL,F());
  }
  else
    return I();
}

void main()
{
  NODE *root;
  getnc();
  root = S();
  if (ch != '$')
    error();
  printf("\nThe post order result is:");
  post_order_walk(root);

}