我有一个正常工作的调车场算法,但我注意到一个特殊的怪癖:
1 + ( 3 * ( 4 + 5 ) )
parses correctly to
1 3 4 5 + * +,
but
1 + (3 * (4 + 5))fails, and parses to
1 * + 5)) +
I want to get it to parse the second problem properly, so that the result is the same as the first. How can I accomplish this?
Notes: I derived my algorithm from wikipedia: http://en.wikipedia.org/wiki/Shunting-yard_algorithm#The_algorithm_in_detail
My algorithm code is:
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”字符开始?然后我只需要将分流的字符串添加到输出 vector ,并在字符串流上调用忽略! 我说的是进行这些更改:
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 循环的末尾。想法?
最佳答案
你的问题是解析器读取字符串:
io >> token;
在我看来,简单的解决方案是一次只读取一个字符。例如。
char ch;
io >> ch;
我实际上会写一个函数来读取一个标记——它会知道诸如“数字序列是一个数字”之类的东西,并将运算符、括号等分开。它会返回一个对象(类或结构类型),它包含“元素类型”和“值(如果相关)”- 因此它可以是类型“数字”和值“4711”,或者类型“运算符”,值“+”。
你的分词器需要一个“状态”,其中包括一个“先行”字符(一个字符应该足够了),这样你就可以在超过数字末尾时停止,然后继续下一次“不再是数字”的角色。
关于c++ - 修改调车场算法 (c++),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16877546/