使用堆栈和二叉树c构建表达式树

Question

我得到了一个包含运算符、、*、和括号的算术公式（这可能会改变运算符的自然优先级，也可能不会改变）。例如：a/b f–（c d）*e–a*c。我被要求使用堆栈（实现为链表）来跟踪操作数和运算符：我的程序应该如何工作的示例如下：

• 读取、推送操作数堆栈
• 读取/推送运算符堆栈
• 读取b，推送操作数堆栈
• Read:的优先级低于/，因此：
  • 从操作数堆栈中弹出2个操作数（a和b）
  • 弹出/来自运算符堆栈
  • 创建子树并推送操作数堆栈
  • 运算符堆栈为空，请按它
  • 从操作数堆栈中弹出2个操作数

  我难以理解的问题是如何区分操作数的优先级！

  以下是我编写的代码的不完整版本：

  #include<stdio.h>
  #include<stdlib.h>
  #include<ctype.h>
  
  typedef struct btnode Btree;
  typedef struct node s_Node;
  
  struct btnode {
      char info; 
      Btree *left; 
      Btree *right;
  };
  
  
  struct node {
      char element;
      s_Node*next;
  }; 
  
  typedef struct{
      s_Node *top_stack;
  } stack_t; 
  
  int IsOperator(char c);
  
  main () {
      FILE* fp;
      stack_t operands;
      stack_t operators;
      char c;
      operands=NewStack();
      operators=NewStack();
      fp= fopen ("Myfile.txt", "r");
      if (fp== NULL)
          printf ("   FILE COULD NOT BE OPENED");
      else
      {
          c=getc(fp);
          while (!feof (fp))
          {
              if ( c== ' ');
              else 
              {
                  printf ("Here is your character: %c\n", c);
                  if (IsOperator (c))
                      Push (c, &operands);
                  else if ( isalpha (c))
  
  
              }
          c=getc(fp);
          }
      }
  }
  
  int IsOperator(char c)
  {   
      switch(c)
      {
          case '+':
          case '-':
          case '/':
          case '*':
          return 1;
          default:
          return 0;
      }
  } 
  
  stack_t NewStack()
  {
      stack_t *n_stack;
      n_stack=(stack_t*)malloc(sizeof(stack_t));
      n_stack->top_stack=NULL;
      return (*n_stack);  
  }
  
  int Push(char e, stack_t *q)
  {       
      s_Node *nn;
      nn= (s_Node*)malloc(sizeof(s_Node));
  
      if(Full(*q))
      {
          printf("\n\t Stack is Full !! \n\n");
          return 0;   // return 0 if enstack NOT successful
      }
      else 
      { 
          nn->element=e; // Storing the elemnt read inside the the new node
          nn->next=q->top_stack; // Pointing the new node to the top of the stack
          q->top_stack=nn; // Changing the top of the stack
          return 1;
      }
  }
  

  提前谢谢你！

Answer 1

对于正在使用的算法，操作数没有优先级。但在自底向上的shift-reduce解析器中，它确实具有优先级，正如@WhozCraig在下面这篇文章的评论中所说的那样。

操作数始终被推入操作数堆栈，并将弹出2，然后使用运算符进行计算，然后作为单个操作数再次推入操作数堆栈。

对于您的公式：a/b f–（c d）*e–a*c

>

a

推送到操作数堆栈

操作数：a

接线员：

/

操作员：/

B

操作员：/

接线员：

f

接线员：

-

接线员：-

（

接线员：-(

C

接线员：-(

操作员：-（

D

操作员：-（

)

接线员：-

*

接线员：-*

E

接线员：-*

-

接线员：-

A.

接线员：-

*

接线员：-*

C

接线员：-*

行结束

结果：（a/b）f）-（c d）*e）-（a*c））