0

我有一个工作正常的调车场算法，但我注意到一个特殊的怪癖：

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 循环的末尾。想法？

4

1 回答 1

1

您的问题是解析器读取字符串：

io >> token;

在我看来，简单的解决方案是一次简单地读取一个字符。例如

char ch;

io >> ch;

我实际上会编写一个读取令牌的函数 - 它会知道诸如“数字序列是数字”之类的东西并分离出运算符、括号等。它将返回一个包含“类型”的对象（类或结构类型）元素”和“值”（如果相关） - 所以它可以是类型“数字”和值“4711”，或者类型“运算符”，值“+”。

您的标记器需要一个“状态”，其中将包括一个“前瞻”字符（一个字符就足够了），这样您就可以在超过数字末尾时停下来，然后拿起那个字符下次“不再是一个数字”。

于 2013-06-01T22:23:38.167 回答