如何將中綴轉換爲多位數操作數的後綴表達式？

Question

我能夠將中綴轉換爲後綴並用一位數進行計算，但我無法轉換爲後綴並使用N位數進行計算。 PLz任何人都可以幫助我！謝謝！！

這裏是我的代碼以個位數

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

using namespace std; 

class infix2postfix 
{ 
public: 
    void push(int symbol); 
    int pop(); 
    void infix_to_postfix(); 
    int priority(char symbol); 
    int isEmpty(); 
    int white_space(char); 
    int eval_post(); 
}; 

char infix[100], postfix[100]; 
int stack[100]; 
int top; 

int main() 
{ 
    infix2postfix ip; 
    top=-1; 
    cout<<"Enter infix : "; 
    gets(infix); 
    ip.infix_to_postfix(); 
    cout<<"Postfix : "<<postfix<<endl; 
    cout<<"Result is : "<<ip.eval_post()<<endl; 
    return 1; 
} 

void infix2postfix :: infix_to_postfix() 
{ 
    int i,p=0; 
    char next; 
    char symbol; 
    for(i=0; i<strlen(infix); i++) 
    { 
     symbol=infix[i]; 
     if(!white_space(symbol)) 
     { 
      switch(symbol) 
      { 
      case '(': 
       push(symbol); 
       break; 
      case ')': 
       while((next=pop())!='(') 
        postfix[p++] = next; 
       break; 
      case '+': 
      case '-': 
      case '*': 
      case '/': 
      case '%': 
      case '^': 
       while(!isEmpty() && priority(stack[top])>= priority(symbol)) 
        postfix[p++]=pop(); 
       push(symbol); 
       break; 
      default: /*if an operand comes*/ 
       postfix[p++]=symbol; 
      } 
     } 
    } 
    while(!isEmpty()) 
     postfix[p++]=pop(); 
    postfix[p]='\0'; /*End postfix with'\0' to make it a string*/ 
} 

/*This function returns the priority of the operator*/ 
int infix2postfix :: priority(char symbol) 
{ 
    switch(symbol) 
    { 
    case '(': 
     return 0; 
    case '+': 
    case '-': 
     return 1; 
    case '*': 
    case '/': 
    case '%': 
     return 2; 
    case '^': 
     return 3; 
    default : 
     return 0; 
    } 
} 

void infix2postfix :: push(int symbol) 
{ 
    if(top>100) 
    { 
     cout<<"Stack overflow\n"; 
     exit(1); 
    } 
    stack[++top]=symbol; 
} 

int infix2postfix :: pop() 
{ 
    if(isEmpty()) 
    { 
     cout<<"Stack underflow\n"; 
     exit(1); 
    } 
    return (stack[top--]); 
} 

int infix2postfix :: isEmpty() 
{ 
    if(top==-1) 
     return 1; 
    else 
     return 0; 
} 

int infix2postfix :: white_space(char symbol) 
{ 
    if(symbol == ' ' || symbol == '\t') 
     return 1; 
    else 
     return 0; 
} 

int infix2postfix :: eval_post() 
{ 
    int a,b,i,temp,result; 
    for(i=0; i<strlen(postfix); i++) 
    { 
     if(postfix[i]<='9' && postfix[i]>='0') 
      push(postfix[i]-'0'); 
     else 
     { 
      a=pop(); 
      b=pop(); 
      switch(postfix[i]) 
      { 
      case '+': 
       temp=b+a; 
       break; 
      case '-': 
       temp=b-a; 
       break; 
      case '*': 
       temp=b*a; 
       break; 
      case '/': 
       temp=b/a; 
       break; 
      case '%': 
       temp=b%a; 
       break; 
      case '^': 
       temp=pow(b,a); 
      } 
      push(temp); 
     } 
    } 
    result=pop(); 
    return result; 
} 

我的問題是：如何獲得超過1位運算的結果？ 我曾嘗試過單個數字，但我怎麼能得到多位數字？

Answer 1

您目前正在單獨推送堆棧上的數字，因此數字值10將被壓入堆棧的兩個符號：1和0。

在您的運算符邏輯中，每個操作數都會從堆棧中彈出一個符號。多位數的操作數將無法工作併產生完全錯誤的結果。

有很多方法可以解決這個問題。例如，您可以在讀取多個數字時將多個數字融合到同一個堆棧符號中（即，如果兩個數字均爲數字，則將當前處理的數字與堆棧頂部合併）。

要做到這一點的地方應該在push之內。以下是如何做到這一點：

void infix2postfix :: push(int symbol) 
{ 
    if(top>100) 
    { 
     cout<<"Stack overflow\n"; 
     exit(1); 
    } 
    if (! isEmpty() && stack[top] >= 0 && stack[top] <= 9) { 
     stack[top] *= 10; 
     stack[top] += symbol; 
    } 
    else { 
     stack[++top]=symbol; 
    } 
} 

這隻要一個數字操作數爲int的範圍內適合的工作。更大的數字將會溢出。

也會有問題，因爲除了其他堆棧符號之外不能告訴數字。使用多位數字，現在可以使用與操作符具有相同int值的符號。解決這個問題的一種方法是爲運算符分配負的int值，併爲數字賦予非負值。這將適用於你的情況，因爲你的語法似乎沒有一元減法。 此方法也符合eval_post中的要求，即將堆棧上的計算結果作爲單個整數值推送，而不管可能包含多少個數字。

最強大但最複雜的替代方法是編寫語法並使用解析器生成器。我建議GNU bison。這將完全接管爲解析器生成代碼，所以你所要做的就是編寫表達式的語法加上實際的中綴到後綴的轉換（這對於野牛來說是微不足道的）。它還將幫助您輕鬆檢測無效輸入並提供適當的錯誤消息。

但是，如果您以前從未使用野牛，開始野牛可能很難。