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

Question

我得到一个包含运算符+, - ,*,/和括号的算术公式(可能会也可能不会改变运算符的自然优先级).一个例子如下:a/b + f - (c + d)*e - a*c.并且我被要求使用堆栈(实现为链接列表)以跟踪操作数和运算符:我的程序应该如何工作的示例如下:

• 读取a,推送操作数堆栈
• 读取/,推动操作员堆栈
• 读b,按下操作数堆栈
• 读+:优先级低于/,所以:
  • 从操作数堆栈中弹出2个操作数(a和b)
  • pop/from operator stack
  • 创建子树并推送操作数堆栈
  • 运算符堆栈为空,因此按下+
• 读取f,按下操作数堆栈
• 读 - :与+具有相同的优先级,因此:
  • 从操作数堆栈中弹出2个操作数
  • pop操作符+来自操作符堆栈
  • 创建一个树,其中operator +为根,两个操作数为left和right子
  • 将创建的树的根推回操作数堆栈
  • 运算符堆栈是空的,所以按下它

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

这是我写的代码的不完整版本:

#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

• 一个
• push 操作数堆栈
• 操作数:a

• 运营商:

• /

• push 到运营商堆栈
• 操作数:a

• 运营商:/

• b

• push 操作数堆栈
• 操作数:ab

• 运营商:/

• +

• +<= /- > pop /,a & b - > a / b - >推送到操作数堆栈
• 推+送到运营商堆栈
• 操作数:(a/b)

• 运营商:+

• F

• 推送到操作数堆栈
• 操作数:(a/b)f

• 运营商:+

• -

• -<= +- > pop +,(a/b)& f - >(a/b)+ f - >推送到操作数堆栈
• 操作数:((a/b)+ f)

• 经营者: -

• (

• 推送到运营商堆栈
• 操作数:((a/b)+ f)

• 经营者: - (

• C

• 推送到操作数堆栈
• 操作数:((a/b)+ f)c

• 经营者: - (

• +

• 推送到运营商堆栈
• 操作数:((a/b)+ f)c

• 运营商: - (+

• d

• 推送到操作数堆栈
• 操作数:((a/b)+ f)cd

• 运营商: - (+

• )

• 直到'('弹出,逐个弹出堆栈中的所有运算符并用2个操作数计算
• - > pop +,c & d - > c + d - >推送到操作数堆栈
• 操作数:((a/b)+ f)(c + d)
• 经营者: - (
• - > pop(,停止弹出操作符堆栈
• 操作数:((a/b)+ f)(c + d)

• 经营者: -

• *

• *> -推送到操作员堆栈
• 操作数:((a/b)+ f)(c + d)

• 运营商: - *

• Ë

• *> -推送到操作数堆栈
• 操作数:((a/b)+ f)(c + d)e

• 运营商: - *

• -

• -<= *pop*,(c + d)& e - >(c + d)*e - >推送到操作数堆栈
• 操作数:((a/b)+ f)((c + d)*e)
• 经营者: -
• -<= -pop - ,((a/b)+ f)&((c + d)*e) - >((a/b)+ f)-((c + d)*e) - >推到操作数堆
• 推送到操作员堆栈
• 操作数:(((a/b)+ f) - ((c + d)*e))

• 经营者: -

• 一个

• 推送到操作数堆栈
• 操作数:(((a/b)+ f) - ((c + d)*e))a

• 经营者: -

• *

• *> -推送到操作员堆栈
• 操作数:(((a/b)+ f) - ((c + d)*e))a

• 运营商: - *

• C

• 推送到操作数堆栈
• 操作数:(((a/b)+ f) - ((c + d)*e))ac

• 运营商: - *

• 行结束

• 逐个弹出堆栈中的所有运算符
• pop*,a&c - >(a*c) - >推送到操作数堆栈
• 操作数:(((a/b)+ f) - ((c + d)*e))(a*c)
• 经营者: -
• pop - ,((((a/b)+ f) - ((c + d)*e))&(a*c) - >(((a/b)+ f) - ((c + d)*e))-(a*c) - >推送到操作数堆栈
• 操作数:(((((a/b)+ f) - ((c + d)*e)) - (a*c))
• 运营商:

结果:(((((a/b)+ f) - ((c + d)*e)) - (a*c))