1

I have implemented shunting-yard algorithm to parse arithmetic string-expressions from infix to postfix-notation. I now also want to parse expressions with relational operators and Ternary conditional. Considering C++ Operator Precedence i added those operators with the lowest precedence and right-associativity for ? and : and the second-lowest and left-associativity for > and <.

When i now parse an expression like: A>B?C:D (where A, B, C and D can be any valid arithmetic expression) i would expect: A B > C D : ?, but i get A B C D : ? <. When i use Parentheses to evaluate the Condition first (A>B)?C:D it works. A mixed expression like (1+2<3+4)?C:D gives me 1 2 + 3 4 + < C D : ? which seems also legit to me. (A<B)?5+6:C gives me A B < 5 6 : + ? which again is messed up. Again, (A<B)?(5+6):C would fix that.

As stated in the comments, evaluating conditions first and the proceed with the left arithmetic expression would also be fine. But i really did not stumble upon an algorithm for evaluating expressions with relational and ternary operators in my research yet. Any help, even if pointing out an algorithm would be very appreciated

Here is the implementation of shunting-yard:

QQueue<QString> ShuntingYard::infixToPostfixWithConditionals(const QString& expression)
{
    QStack<QString> stack;
    QQueue<QString> queue;
    QString token;
    QStringList tokens = splitExpression(expression);
    Q_FOREACH(QString token, tokens)
    {
        if (isDefineOrNumber(token))
            queue.enqueue(token);
        if (isFunction(token))
            stack.push(token);
        if (isOperator(token))
        {
            while (!stack.isEmpty() && isOperator(stack.top()) && isLeftAssociativeOperator(token) && !hasHigherPrecedence(token, stack.top()))
                queue.enqueue(stack.pop());
            stack.push(token);
        }
        if (isLeftParenthese(token))
            stack.push(token);
        else if (isRightParenthese(token))
        {
            while (!isLeftParenthese(stack.top()))
            {
                if (stack.isEmpty())
                    break;
                if (isOperator(stack.top()))
                    queue.enqueue(stack.pop());
            }
            stack.pop();
            if (isFunction(stack.top()))
                queue.enqueue(stack.pop());
        }
    }
    while (!stack.isEmpty())
    {
        if (isLeftParenthese(stack.top()))
            break;
        queue.enqueue(stack.pop());
    }
    return queue;
}

EDIT: made code and description more concise for readabilility

Another EDIT: Treating ?: as left-associative gave me the expected output

Now, regarding this question about the associativity of ternary conditionals. If i input a<b?a:b?c:d i get a b < a b c d : ? : ?, where a < b will be evaluated first, which is correct, due to its higher precedence, but then b ? c : d will be evaluated first, which is the correct right-to-left order. Confusing.

Community
  • 1
  • 1
tobilocker
  • 891
  • 8
  • 27
  • The ternary operator is tricky in this scenario as you don't want to evaluate the `true` and `false` part and push them onto the stack, so the only part that should be evaluated is the part that maps to the outcome of the comparison. – Sean May 18 '16 at 14:10
  • @Sean i could either live with using `0` and `not 0` to evaluate the ternary expression or parsing the ternary expression first to then evaluate the left arithmetic expression but i'm really stuck on this one for now. Edit: i would actually prefer a solution for parsing something like `A – tobilocker May 18 '16 at 14:14
  • 1
    Don't tag C++ questions as C. Don't tag C questions as C++. Only tag a question with both if it's about the differences in the languages. (Removed the C tag.) – DevSolar May 18 '16 at 14:15
  • @DevSolar Thanks for pointing out. That must have been slipped in within the suggestions. Sry – tobilocker May 18 '16 at 14:17
  • The shunting-yard algorithm will handle relational operators without any problem whatsoever but it is not designed for ternary operators, function calls, and so on. Time to look at a parser-generator solution. – user207421 May 19 '16 at 10:26
  • It handles functions without problems – tobilocker May 19 '16 at 10:34

0 Answers0