修改分流算法（c ++） [英] Modifying the Shunting Yard Algorithm (c++)
问题描述
1 +（3 *（4 + 5））我有一个正常工作顺序的调车场算法，但我注意到一个特殊的怪癖：
正确解析
1 3 4 5 + * +，
但
1 +（3 *（4 + 5））
失败， / p>
1 * + 5））+
我想让它解析第二个问题正确，使结果与第一个相同。我如何实现这一点？
注意：
我从维基百科中导出了我的算法：
http://en.wikipedia.org/wiki/Shunting-yard_algorithm#The_algorithm_in_detail
我的算法代码是：
string switchingYard（string input）
{
stringstream io输入）;
ProcessStack switch_stack;
vector< string>出口;
while（io.good（））
{
string token;
io>>令牌
if（isdigit（token [0]）||（token [0] =='。'&& isdigit（token [1]））
||（（token [0] =' - '&&& isadigit（token [1]））||（token [0] ==' - '& ]））））
{
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）
returnMISMATCH_ERROR;
}
if（isOperator [0]））
{
while（isOperator（switch_stack.peekChar（））&&
（left_assoc（token [0]）& 0]）== op_preced（switch_stack.peekChar（））））||（op_preced（token [0]）
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）
returnMISMATCH_ERROR;
string parensPop = switch_stack.popNode（）;
if（isFunctionToken（switch_stack.peek（）））
{
string funcPop = switch_stack.popNode（）;
out.push_back（funcPop）;
}
b $ b}
}
while（switch_stack.length（）> 0）
{
if（switch_stack.peekChar（）=='（'|| switch_stack.peekChar （）=='）'）
returnMISMATCH_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：\\\
< ret<< endl;
return ret;
}
编辑：好吧，因此，当解析器遇到（3）标记时，它会将两个字符视为一个，并丢弃整个事物，但如果我调用函数递归，传入输入字符串从'3'字符开始？然后我只需要添加分流的字符串到输出向量，并在stringstream上调用ignore
我在说这些更改：
string switchingYard（string input）
成为
string switchingYard（string input，int depth）
if（（token [0] =='（'|| token [0] =='）'）& ]）|| token [1] =='。'|| isOperator（token [1]））
{
string shunted_recur = out.push_back（switchingYard（input.substr（io.tellg +1），depth + 1））;
}
被添加到while循环的结尾。您的问题是解析器读取字符串：
<$> c $ c> io>>令牌
在我看来，简单的解决方案是一次只读一个字符。例如。
char ch;
io>> ch;
我实际上会写一个读取令牌的函数 - 它会知道是一个数字和分离的运算符，括号等。它将返回一个保存类型的元素和值（如果相关）的对象（类或结构类型） - 所以它可以是类型数字 4711或键入operator，值+。
您将需要一个状态，包括一个lookahead字符一个字符应该足够了），这样你可以停止，当你已经走过一个数字的结尾，然后拿起下一次停止是一个数字的字符。
I have a shunting yard algorithm in proper working order, but I noticed a special quirk:
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;
}
Edit: Ok, so I just got an idea. So when the parser encounters the '(3' token, it would otherwise treat the two characters as one, and discard the whole thing, but what if I called the function recursively, passing in the substring of the input string which starts at the '3' character? I would then only need to add the shunted string to the output vector, and call ignore on the stringstream! I'm talking about making these changes:
string switchingYard(string input)
becomes
string switchingYard(string input, int depth)and
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));
}gets added to the end of the while loop. Thoughts?
Your problem is that the parser reads strings with:
io >> token;
The simple solution, in my opinion, would be to simply read a character at a time. E.g.
char ch;
io >> ch;
I would actually write a function that reads a token - it would know things like "a sequence of digits is a number" and separate out operators, parenthesis, etc. It would return an object (class or structure type) that holds an "type of element" and "value (if relevant) - so it could be type "number" and value "4711", or type "operator", value "+".
You will need a "state" for your tokeniser, which will include a "lookahead" character (one char should be enough), so that you can stop when you have gone past the end of a number, and then pick up the character that "stopped being a number" next time around.
这篇关于修改分流算法（c ++）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
