2013-03-02 154 views
1

我一直在试图调试这个程序很长一段时间。当我输入表达式 ,比如a + b-c或a/b + c,其中第一个运算符的优先级大于或等于第二个运算符时,它工作正常。但对于像a-b/c这样的表达式,第一个运算符比第二个运算符具有更低的优先级,编译器将引发一个断点。使用C中的链接列表插入到postfix实现中

struct stack 
{ 
    char ele; 
    struct stack *next; 
}; 

void push(int); 
int pop(); 
int precedence(char); 

struct stack *top = NULL; 

int main() 
{ 
    char infix[20], postfix[20]; 
    int i=0,j=0; 

    printf("ENTER INFIX EXPRESSION: "); 
    gets(infix); 

    while(infix[i]!='\0') 
    { 
    if(isalnum(infix[i])) 
     postfix[j++]=infix[i]; 
    else 
    { 
     if(top==NULL) 
      push(infix[i]); 

     else 
     { 
     while(top!=NULL && (precedence(top->ele)>=precedence(infix[i]))) 
       postfix[j++]=pop(); 
      push(infix[i]); 
     } 
    } 

    ++i; 
} 

    while(top!=NULL) 
    postfix[j++]=pop(); 

    postfix[j]='\0'; 
    puts(postfix); 
    getchar(); 
    return 0; 
} 

int precedence(char x) 
{ 
    switch(x) 
    { 
    case '^': return 4; 
    case '*': 
    case '/': return 3; 
    case '+': 
    case '-': return 2; 

    default: return 0; 
    } 
} 

void push(int x) 
{ 
int item; 
struct stack *tmp; 

if(top==NULL) 
{ 
    top=(struct stack *)malloc(sizeof(struct stack)); 
    top->ele=x; 
    top->next=NULL; 
} 

else 
{ 
    tmp=top; 
    top->ele=x; 
    top->next=tmp; 
} 
} 

int pop() 
{ 
    struct stack *tmp; 
    int item; 

    if(top==NULL) 
    puts("EMPTY STACK"); 

    else if(top->next==NULL) 
    { 
    tmp=top; 
    item=top->ele; 
    top=NULL; 
    free(tmp); 
} 

else 
{ 
    tmp=top; 
    item=top->ele; 
    top=top->next; 
    free(tmp); 
} 

return item; 
} 

任何关于如何改善我的编码的建议将是有帮助的。 感谢您的帮助,我真的很感激:)

+5

当我看到代码和这样的任务,我总是感谢上帝被给智能计算机科学家递归下降解析器的想法... – 2013-03-02 11:08:27

+1

为了解析,认为“树”。例如,表达式“1 + 2”可以看作一棵以'+'为根节点的树,以及'1'和'2'为子节点。拥有这样一棵树后,它很容易以后缀,前缀或中缀表示法输出。诸如[递归下降](http://en.wikipedia.org/wiki/Recursive_descent_parser)之类的技术所做的就是在堆栈中创建该树,而不是手动创建树结构,虽然后者更灵活。递归下降也非常好。 – 2013-03-02 11:13:50

+2

“编译器抛出断点”是什么意思? – 2013-03-02 12:04:02

回答

0
it works fine for me. 


#include<stdio.h> 
#include<stdlib.h> 
#include<string.h> 

struct node 
{ 

char data; 
struct node *next; 


}*top=NULL,*pstart=NULL; 
/*-------------------- insertion in postfix expression linked list -------*/ 


void insert(char ch) 
{ 
struct node *t,*baby; 
    baby=(struct node *)malloc(sizeof(struct node)); 
    baby->next=NULL; 
    baby->data=ch; 
    t=pstart; 

    if(pstart==NULL) 
    { 
    pstart=baby; 
    } 
    else 
    { 
    while(t->next!=NULL) 
    t=t->next; 
    t->next=baby; 

    } 
    //printf(" inserted in list- %c",baby->data); 

} 

/* --------- push operation ------- */ 



void push (char symbol) 
{ 

    struct node *p; 
    p=(struct node *)malloc(sizeof(struct node)); 
    p->data=symbol; 
    if(top==NULL) 
    { 
    top=p; 
    p->next=NULL; 

    } 
    else 
    { 

    p->next=top; 
    top=p; 

    } 
} 

char pop() 
{ 
struct node *x,*y; 
char k; 
if(top==NULL) 
{ 
    printf("stack underflow\n"); 
    return 0; 

} 
else 
{ 
x=top; 
top=top->next; 
k=x->data; 
//printf("node %d is deleted\n",top->data); 
free(x); 
x=NULL; 
return k; 


} 



} 


void displaypost() 
{ 
    struct node *to; 
    if(pstart==NULL) 
    printf(""); 
    else`enter code here` 
    { 
    to=pstart; 
    while(to!=NULL) 
    { 
     printf("%c",to->data); 
     to=to->next; 

    } 

    } 


} 


/*============== precedence selector ================= */ 

int precedence(char ch) 
{ 

if(ch=='^') 
return (5); 
else if(ch=='*' || ch== '/') 
return (4); 
else if (ch== '+' || ch== '-') 
return (3); 
else 
return (2); 
} 


/*=================== infix to postfix conversion ================ */ 

void intopost(char infix[]) 
{ 

    int len; 
    int index=0; 
    char symbol,temp; 
    len= strlen(infix); 
    //printf("%d",len); 
    while(len>index) 
    { 
     symbol=infix[index]; 

     switch(symbol) 
     { 

     case '(': 
     push(symbol); 
     break; 

     case ')': 
     temp=pop(); 
     while(temp!='(') 
     { 
     insert(temp); 
     temp=pop(); 
     } 
     break; 

     case '^': 
     case '+': 
     case '-': 
     case '*': 
     case '/': 
     if(top==NULL) 
     { 
      push(symbol); 
    //  break; 

     } 
     else 
     { 
     while(top!=NULL && (precedence(top->data)>=precedence(symbol))) 
     { 
      temp=pop(); 
      insert(temp); 

     } 
     push(symbol); 

     } 
     break; 
     default: 
     insert(symbol); 

     } 
     index=index+1; 


    } 
    while(top!=NULL) 
    { 
    temp=pop(); 
    insert(temp); 

    } 
    displaypost(); 
    return; 




} 


int main() 
{ 
char infix[50]; 
system("clear"); 
printf("enter infix expression: "); 
gets(infix); 

printf("\n\n equivalent postfix expression is---> "); 
intopost(infix); 
getchar(); 
return 0; 
} 
`