изменяющие Шунтирование Yard Алгоритм (с ++)

Question

У меня есть алгоритм сортировочной станции в надлежащем рабочем состоянии, но я заметил особую странность:

1 + (3 * (4 + 5))

правильно разбирает к

1 3 4 5 + * +,

но

1 + (3 * (4 + 5))

терпит неудачу , и анализирует до

1 * + 5)) +

Я хочу получить его для анализа секона 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; 
} 

Edit: Хорошо, так что я только что получил идею. Поэтому, когда парсер встречает токен (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.

Answer 1

Ваша проблема в том, что анализатор читает строки с:

io >> token; 

Простое решение, на мой взгляд, было бы просто читать посимвольно. Например.

char ch; 

io >> ch; 

Я бы на самом деле написать функцию, которая читает маркер - это было бы знать такие вещи, как «последовательность цифр является числом» и выделят оператор, круглые скобки и т.д. Было бы вернуть объект (класс или структуру тип), который содержит «тип элемента» и «значение (если применимо), поэтому он может быть« число »и значение« 4711 », или введите« оператор », значение« + ».

Вам понадобится «состояние» для вашего токенизатора, в которое будет входить «внешний вид» (один символ должен быть достаточным), чтобы вы могли остановиться, когда вы прошли конец номера, а затем забрать персонажа, который «перестает быть число "в следующий раз.