0

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

  • 读a,压入操作数栈
  • 读取 /,推入操作符栈
  • 读取 b,压入操作数堆栈
  • 读取 +: 的优先级低于 / ,因此:
    • 从操作数堆栈中弹出 2 个操作数(a 和 b)
    • 弹出/从运算符堆栈
    • 创建子树并压入操作数堆栈
    • 运算符堆栈是空的,所以按 + 就可以了
  • 读取 f,压入操作数堆栈
  • 读取 - : 与 + 具有相同的优先级,因此:
    • 从操作数堆栈中弹出 2 个操作数
    • 从运算符堆栈中弹出运算符 +
    • 创建一个以运算符 + 作为根,两个操作数作为左右子节点的树
    • 将创建的树的根推回操作数堆栈
    • 运算符堆栈是空的,所以 push - 就可以了

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

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

#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;
    }
}

先感谢您!

4

1 回答 1

5

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

操作数总是被压入操作数堆栈,并会被弹出 2 并使用运算符计算,然后作为单个操作数再次压入操作数堆栈。

对于您的公式:a / b + f – (c + d) * e – a * c

  • 一种
  • push到操作数栈
  • 操作数:一个
  • 运营商

  • /

  • push到运算符堆栈
  • 操作数:一个
  • 运营商:/

  • b

  • push到操作数栈
  • 操作数:ab
  • 运营商:/

  • +

  • +<= /-> pop /, a & b -> a / b -> push 到操作数栈
  • +入操作栈
  • 操作数:(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)
  • 运营商: - *

  • e

  • *>-推入操作数堆栈
  • 操作数: ((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) -> 推入操作数堆
  • push - 到操作符栈
  • 操作数:(((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) -> push 到操作数栈
  • 操作数:(((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))

于 2012-12-08T14:10:39.803 回答