中綴到Postfix轉換錯誤

Question

我正在寫一個基本程序，用於將中綴表示法中的表達式轉換爲使用堆棧的後綴表示法。

這是我的程序。

#include<stdio.h> 
#include<stdlib.h> 
#include<stdbool.h> 
#include<string.h> 
#define MAX_STACK_SIZE 100 

//STACK IMPLEMENTATION BEGINS 
struct stack{ 
    int top; 
    char items[MAX_STACK_SIZE]; 
}; 
void push(struct stack* s, char n){ 
    if(s->top==MAX_STACK_SIZE-1) 
     printf("Stack Overflow. Cannot push\n"); 
    else 
     s->items[++s->top]=n; 
} 
bool isempty(struct stack* s){ 
    if(size(s)==0) 
     return 1; 
    else return 0; 

} 


char pop(struct stack* s){ 
if(isempty(s)) 
{printf("\nStack Underflow. Cannot Pop\n"); 
return 0;} 
else 
{return (s->items[s->top--]); 
} 
} 

bool isfull(struct stack* s){ 
    if(size(s)==MAX_STACK_SIZE) 
     return 1; 
    else return 0; 

} 
void display(struct stack* s){ 
    int num; 
    if(isempty(s)) 
     printf("Stack empty. Nothing to display\n"); 
    else 
    { 
     for(num=0;num<=s->top;num++) 
      printf("%d ",s->items[num]); 
    } 

} 
int size(struct stack* s){ 
    if(s->top==-1) 
     return 0; 
    else 
return (s->top+1); 


} 
//STACK IMPLEMENTATION ENDS 

//checks if a character entered is an operator or not 
bool isOperator(char ch){ 
    if(ch=='-'||ch=='+'||ch=='*'||ch=='/') 
     return true; 
    else 
     return false; 
} 
//checks if a character entered is an operand(0-9) or not 
bool isOperand(char ch){ 
    if(ch>=48 && ch<=57) 
     return true; 
    else 
     return false; 


} 
//decides the precedence of operators 
int precedence(char ch){ 
    if(ch=='*'||ch=='/') 
     return 2; 
    if(ch=='+'||ch=='-') 
     return 1; 

} 
void main(){ 
/* 
    /*Declarations Begin*/ 
    char infix_exp[50],ch; 
    int a;  
    struct stack s; 
    s.top=-1; 
    /*Declarations End*/ 

    printf("Enter your infix expression\n"); 
    scanf("%s",&infix_exp); 
    for(a=0;a<strlen(infix_exp);a++)//scanning the entire array 
    { 
     if(isOperator(infix_exp[a])){ 
       while(s.top>=0 && isOperator(s.items[s.top])) 
      { 
        if(s.items[s.top]=='('|| isempty(&s)) 
        { 
         push(&s,infix_exp[a]); 

        } 
        if(isOperator(s.items[s.top])){ 
         while((s.top--)>=0){ 
         if(precedence(infix_exp[a])>=precedence(s.items[s.top])) 
         { 
          ch=pop(&s); 
          printf("%c",ch); 

         push(&s,infix_exp[a]); 
         } 
         else 
         { 
          push(&s,infix_exp[a]); 
         }}}}} 
     if(isOperand(infix_exp[a])){printf("%c",infix_exp[a]);} 
     if(infix_exp[a]=='('){push(&s,'(');} 
     if(infix_exp[a]==')'){ 
      while(s.top>=0 && s.items[s.top]!='(') 
      { 
       ch=pop(&s); 
       printf("%c",ch); 

      } 
      pop(&s); 
     }}} 

這裏是輸出。

Enter your infix expression 
6+1 
61 
RUN FINISHED; exit value 3; real time: 4s; user: 0ms; system: 0ms 

我遵循的邏輯就是這樣。

用戶輸入他的表達式後，程序會掃描每個元素。 如果元素是一個操作數，它將被打印。 如果元素是開口支架，則將其推入堆棧。 如果元素是右括號，堆棧中的每個元素都會彈出並打印，直到遇到相應的左括號。 如果元素是操作者（通過isOperator()功能檢查），那麼該堆棧的頂部元件可以是三個中的一個，

1. 開括號-的元件被簡單地壓入堆棧;
2. 空即堆棧爲空 - 元素簡單地推入堆棧;
3. 另一個運算符 - 然後遍歷堆棧並且中綴表達式元素的優先級（precedence()）大於或等於堆棧頂部元素的優先級，那麼堆棧頂部被彈出並打印並且中綴表達式元素是推。否則，只有中綴表達式元素被推入，沒有東西被彈出。

我無法獲得輸出中的運算符。什麼可能是錯誤？我可能是一個微不足道的人，可能是打印價值觀，或者可能是我的邏輯。任何幫助讚賞。

Answer 1

看起來你正在使用Shunting-yard algorithm，但有一些事情你做錯了。

首先，算法運行後，您仍然必須打印出棧中剩餘的內容並檢查不匹配的parens。由於維基文章說：

1. 當沒有更多的標記閱讀
2. 雖然仍然在堆棧操作標記：
   • 如果在堆棧的頂部的操作令牌一個括號，然後有不匹配的括號。
   • 將操作員彈出到輸出隊列中。

這是很容易添加到您的代碼，只需添加這樣的事情後，for循環：

while(!isempty(&s)) 
{ 
    ch = pop(&s); 
    if(ch == ')' || ch == '(') { 
     printf("\nMismatched parens\n"); 
     break; 
    } 
    printf("%c",ch); 
} 

但這並不解決問題的時候了，因爲還有另一個問題。

的第二個問題是在當前輸入令牌是一個操作符，這個你說的情況：

如果元素是一個操作符（由isOperator（）函數選中），然後棧頂元素堆棧可以是三個之一，

1. 開口支架 - 該元素被簡單地推到堆棧上;
2. 空即堆棧爲空 - 元素簡單地推入堆棧;
3. 另一個運算符 - 然後遍歷堆棧，並且是中綴表達式元素的優先級（precedence（））大於或等於堆棧頂部元素的優先級，那麼棧頂將被彈出並打印。而中綴表達式元素被推送。否則，只有中綴表達式元素被推入，沒有東西被彈出。

這說明基本上是正確的，但我覺得你有你的優先倒退，而你只應該在年底推到輸出隊列一次（而不是一次的每個元素堆棧）。

但是你的代碼不符合它。

這裏是你的代碼的相關部分與評論註解

//if the input token is an operator 
if(isOperator(infix_exp[a])) 
{ 
    //while s isn't empty and has an operator on top 
    while(s.top>=0 && isOperator(s.items[s.top])) 
    { 
     //if the top element is a '(' (NEVER HAPPENS because '(' isn't an operator) 
     if(s.items[s.top]=='('|| isempty(&s)) 
     { 
      push(&s,infix_exp[a]); 
     } 
     //If the top element is an operator (ALWAYS HAPPENS) 
     if(isOperator(s.items[s.top])) 
     { 
      //discard the top element of the stack, loop while there are still elements left 
      while((s.top--)>=0) 
      { 
       //if the top element of the stack (after the one that was discarded) has precedence 
       //then pop it to the output queue and push the input token to the stack 
       if(precedence(infix_exp[a])>=precedence(s.items[s.top])) 
       { 
        ch=pop(&s); 
        printf("%c",ch); 
        push(&s,infix_exp[a]); 
       } 
       //otherwise push the input token to the stack 
       else {     
        push(&s,infix_exp[a]); 
       } 
      } 
     } 
    } 
} 

注意的if語句永遠不會觸發之一。你有兩個while循環迭代堆棧，其中一個實際上沒有做任何迭代。您在第二個while循環中將堆棧縮小到兩個不同的位置。輸入令牌可以被推送輸出多次。

總的來說，這只是一個大混亂。

現在讓我們看一下（再根據維基百科）算法說做（約蘇茨基格式不好意思）：

1. 如果令牌是一個運營商，O1，則：

2. 同時有操作者的令牌，O 2，在該堆的頂部，並且

   任O1是向左結合和其優先級等於O2

   的

   或O1具有優先級小於O2的，

   • 彈出O2從堆棧，到輸出隊列。

3. 將o1推入堆棧。

這並不真正符合上面的代碼，但會是什麼？

好第一部分是對

//if the input token is an operator 
if(isOperator(infix_exp[a])) 
{ 

然後你需要使用一個循環檢查，看是否有在堆棧的頂部適當的優先級的運營商：

//Traverse stack while the precedence is right 
    while(!isempty(&s) && isOperator(s.items[s.top]) 
      && (precedence(infix_exp[a]) <= precedence(s.items[s.top]))) 
    { 

並從迴路中彈出：

 ch = pop(&s); 
     printf("%c",ch); 
    } 

最後將輸入令牌推入堆棧：

push(&s, infix_exp[a]); 
}