Модификация алгоритма маневрового двора (c ++)

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

1 + (3 * (4 + 5))

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

1 3 4 5 + * +,

но

1 + (3 * (4 + 5))

не удается, и анализирует

1 * + 5)) +

Я хочу, чтобы он правильно проанализировал вторую проблему, чтобы результат совпадал с первой. Как я могу сделать это?

Заметки:
Я вывел свой алгоритм из Википедии:
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»? Тогда мне нужно будет только добавить шунтированную строку в выходной вектор и вызвать ignore в потоке строки!
Я говорю о внесении этих изменений:

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. Мысли?

0

Решение

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

io >> token;

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

char ch;

io >> ch;

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

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

1

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]