前綴中綴不太給出正確的結果

Question

我有一個非常簡單的算法，需要一個RPN字符串，並將其轉換爲中綴：

for(unsigned int i = 0; i < tokens.size(); i++) 
    { 
     token = tokens[i]; 

     if(!isOperator(token)) 
     { 
      stack.push(token); 
     } 
     else 
     { 
      //need at least 2 values 
      string a = stack.pop(); 
      string b = stack.pop(); 
      string expr = "(" + a + token + b + ")"; 
      stack.push(expr); 
     } 
    } 

string converted = stack.pop(); 

然而，我的RPN字符串也有它的指數。

下面是一個簡單的RPN：

3 4 2 * 1 5 - 2 3^^/+ 

綴樣子：

(3+((4*2)/((1-5)^(2^3)))) 

這是正確的。

我修改這個前綴的工作：

for(int i = tokens.size() - 1; i >= 0; i--) 
    { 
     token = tokens[i]; 

     if(!isOperator(token)) 
     { 
      stack.push(token); 
     } 
     else 
     { 
      //need at least 2 values 
      string a = stack.pop(); 
      string b = stack.pop(); 
      string expr = "(" + a + token + b + ")"; 
      stack.push(expr); 
     } 
    } 

但是它給出了一個稍微不同的結果：

鑑於前綴：

+ 3 * 4/2^^ - 1 5 2 3 

我得到的綴：

(3+(4*(2/(((1-5)^2)^3)))) 

W這有點不對。我不知道爲什麼4乘以表達式的其他部分而不是2。

任何人都可以指向我什麼可能是錯的？

謝謝

Answer 1

您的算法是正確的。你得到了錯誤的答案，因爲你的測試輸入錯誤。

爲相應的中綴的前綴應該是

+ 3/* 4 2^- 1 5^2 3 

有關prefix notation（波蘭式）的信息我要審閱。