修改調度場算法（C++）

我在正確的工作順序調度場算法，但我注意到一個特殊的怪癖：修改調度場算法（C++）

1 + (3 * (4 + 5))

正確解析到

1 3 4 5 + * +,

但

1 + (3 * (4 + 5))

失敗，並解析爲

1 * + 5)) +

我想讓它解析secon d問題，以便結果與第一個相同。我怎樣才能做到這一點？

注：我得出我的算法從維基百科： http://en.wikipedia.org/wiki/Shunting-yard_algorithm#The_algorithm_in_detail

我的算法代碼是：

string switchingYard(string input) 
{ 
stringstream io(input); 
ProcessStack switch_stack; 
vector<string> out; 
while(io.good()) 
{ 
    string token; 
    io >> token; 
    if(isdigit(token[0]) || (token[0] == '.' && isdigit(token[1])) 
     || ((token[0] == '-' && isdigit(token[1])) || (token[0] == '-' && token[1] == '.' && isdigit(token[2])))) 
    { 
     out.push_back(token); 
    } 


    if(isFunctionToken(token)) 
    { 
     switch_stack.pushNode(token); 
    } 

    if(isArgSeparator(token[0])) 
    { 
     bool mismatch_parens = false; 
     do{ 
      if(switch_stack.length() == 1) 
      { 
       if(switch_stack.peekChar() != '(') 
       { 
        mismatch_parens = true; 
        break; 
       } 
      } 
      string opPop = switch_stack.popNode(); 
      out.push_back(opPop); 
     }while(switch_stack.peekChar() != '('); 
     if(mismatch_parens) 
      return "MISMATCH_ERROR"; 
    } 

    if(isOperator(token[0])) 
    { 
     while( isOperator(switch_stack.peekChar()) && 
       ((left_assoc(token[0]) && (op_preced(token[0]) == op_preced(switch_stack.peekChar()))) || (op_preced(token[0]) < op_preced(switch_stack.peekChar())))) 
     { 
      string popped = switch_stack.popNode(); 
      out.push_back(popped); 
     } 
     switch_stack.pushNode(token); 
    } 

    if(token == "(") 
     switch_stack.pushNode(token); 

    if(token == ")") 
    { 
     bool mismatch_parens = false; 
     while(switch_stack.peekChar() != '(') 
     { 
      if(switch_stack.length() == 0 || (switch_stack.length() == 1 && switch_stack.peekChar() != '(')) 
      { 
       mismatch_parens = true; 
       break; 
      } 
      string opPop = switch_stack.popNode(); 
      out.push_back(opPop); 
     } 
     if(mismatch_parens) 
      return "MISMATCH_ERROR"; 
     string parensPop = switch_stack.popNode(); 
     if(isFunctionToken(switch_stack.peek())) 
     { 
      string funcPop = switch_stack.popNode(); 
      out.push_back(funcPop); 
     } 

    } 
} 
while(switch_stack.length() > 0) 
{ 
    if(switch_stack.peekChar() == '(' || switch_stack.peekChar() == ')') 
     return "MISMATCH_ERROR"; 
    string opPop = switch_stack.popNode(); 
    out.push_back(opPop); 
} 
string ret; 
for(int i = 0; (unsigned)i < out.size(); i++) 
{ 
    ret += out[i]; 
    if((unsigned)i < out.size()-1) 
     ret += " "; 
} 
cout << "returning:\n" << ret << endl; 
return ret; 
}

編輯：好了，我只是有一個想法。因此，當解析器遇到'（3'標記，否則它會將兩個字符視爲一個，並放棄整個事情，但如果我遞歸地調用函數，傳入輸入字符串的子字符串？在「3」字我就那麼只需要接受分流的字符串添加到輸出載體，並呼籲忽略對stringstream的我說的做了這些改變：

string switchingYard(string input)

成爲

string switchingYard(string input, int depth)

和

if((token[0] == '(' || token[0] == ')') && (isdigit(token[1]) || token[1] == '.' || isOperator(token[1])) 
      { 
       string shunted_recur = out.push_back(switchingYard(input.substr(io.tellg()+1),depth+1)); 
      }

被添加到while循環的末尾。想想嗎？

來源

2013-06-01 Chuck Rittenhouse