Hacker News Reader

Comment by ReDress | Hacker News Reader

I'm not sure whether someone else has commented on this. I am yet to read the comments. Maybe I will read them soon enough.

Anyways and however, speaking in strict mathetical sense, the model of a tree actually breaks the classical mathematical model of operator precedence.

1 + 1 + 1 evaluates to:

     (+)
     / \
   (+) (1)
   / \
 (1) (1)

The above will be correct, mathematically, but will break once you involve multiple mathematical operators in the statement. Because, mathematically, operators have precedence.

The operators are essentially ordered based on their depth into the right of the question / statement but unless I am terribly wrong, this is not the case in mathematics and some operators have higher precedence regardless of their position in the statement.

Any comments on this?

View on HN

Operator precedence needs to get applied at parsing time, before you get a tree. 1 + 2 * 1 needs to get parsed to

     (+)
     / \
   (1) (*)
       / \
     (2) (1)

The tree representation is unambiguous and once you get that there's no need to think about precedence.

There's many ways to do this parsing, e.g. https://matklad.github.io/2020/04/13/simple-but-powerful-pra...

Agree with 'solve it during parsing'.

I had a look at the link. The BNF looked good:

  Expr =
    Expr '+' Expr
    ...

Then the author fixed the left-recursion and precedence (which also looks good,) but then complains about the fixed version - "the “shape” of expressions feels completely lost in this new formulation." :

  Expr =
    Factor
  | Expr '+' Factor
  ...

Then the author takes us through Pratt parsing and ends up at:

  fn expr_bp(lexer: &mut Lexer, min_bp: u8) -> S { 
    let mut lhs = match lexer.next() {
        Token::Atom(it) => S::Atom(it),
        t => panic!("bad token: {:?}", t),
    };

    loop {
        let op = match lexer.peek() {
            Token::Eof => break,
            Token::Op(op) => op,
            t => panic!("bad token: {:?}", t),
        };
    ...

Yikes! I think he criticised the wrong code. I'll take the '{expression} is a {factor} or an {expression plus a factor}' formulation over the 'mut-loop-peek-panic-lexer-next' approach any day!

We could give weight to operators. Operators that are heavier go further down the three (have precedence) while the lighter ones float.

1+2*3^(4+1)+2/3

We start the evaluation with 1+, the chain would be on (+) for now.

       (+) <
       / 
     (1)

The next operator is (*), and because this one is heavier it falls down, bringing 2 with it.

       (+) 
       / \
     (1) (*) <
         /
        (2)

Now checking the next operator (^), once again heavier, goes down the three.

       (+) 
       / \
     (1) (*)
         / \
       (2) (^) <
           /
         (3)

The next operation is between parenthesis, that takes precedence and goes down, but the pointer comes up after the operation has taken place.

       (+) 
       / \
     (1) (*)
         / \
       (2) (^) <
           / \
         (3) (+)
             / \
            (4) (1)

Next operation is (+), this one floats, and as it's the same weight at the root it doesn't matter its relationship with it, so we put it higher.

        (+) <
        / \
       (+) 2
       / \
     (1) (*)
         / \
       (2) (^)
           / \
         (3) (+)
             / \
            (4) (1)

Finally we got the division, which is heavier again.

         (+)
         /  \
       (+)   (/)
       / \    / \
     (1) (*) (2) (3)
         / \
       (2) (^)
           / \
         (3) (+)
             / \
            (4) (1)

Did this on the fly, so it might have edge cases, but it works well as a starting point.

Thank you!

Turns you have a fairly, if not a very complicated tree for a simple problem. But, fair, enough, you can always get AI to write the code for this and probably, the code will be reused over and over.

But, is it just me or does someone else think that having to rebalance or re-order the tree might be a good breaking point for the camels back?

:-)

If you want to have the full operation recorded this is the way to do it. Either this or a non-binary tree in where multiple operators with the same operand and level are all together:

         (+)   
       /  |  \
     (1) (*)  (/)
        / |    | \
      (2) (^) (2) (3)
          / \
        (3) (+)
            / \
          (4) (1)

If you transform the mathematical operation to lisp terms you will have the tree explicitly written.

The only way that I can think of to make it simpler is to go the array language route of going right to left and ignore precedence, or some similar way of working.

The code to create the tree should not complex, so yes, AI could be used, but most competent coders should be able to create a basic version and test it in an afternoon.

If you are parsing left to right it can be quite easy to balance things, you should not need rebalancing at all. When you are in an operation node and you have to add an operation of the same level of priority, you always get the existing operation and subtree, put it on the left of the new operation, and continue from there.

With this if you try to do - next to a - or +, or a / to a / or *, you'll be preserving the order of the operations, and the calculation will be correct. Try it with 2*3/4.

       (*)   
       / \
     (2) (3)

        (/)
        / \
       (*) (4) 
       / \
     (2) (3)

If you add some more operations to the right (*2/5*12/7) you keep growing the tree. It will not be balanced, but it doesn't need to be.

>The code to create the tree should not complex, so yes, AI could be used, but most competent coders should be able to create a basic version and test it in an afternoon.

I generally tend to find the idea of 'competent' coders misleading. For the most part, I have been developing or writing code in a certain language for while, then it turns out that I am competent coder? Because, yeah, I've been using C or Python for a while and can easily solve a lot of "complex" problems in C but with all due respect, I am obviously not a competent coder. It's like a situation where you frequent a certain part of town that you're very familiar with it and the people living there but then at the same time you don't live there - lol.

Anyways, for this problem I would parse this statement but definitely not into a tree. I'd assign the integrals to objects. I would then parse or go through the statement again executing the operands.

Well...

I'm not saying that competent coders will see the problem and think about doing trees and code it that way. I'm saying that if you have that problem and want to solve it with trees (so knowing the problem and a solution) they should be able to program it.

And in a way you are solving it the same way, if I understood you correctly.

Assuming you mean that you'd have classes, and create objects with the operations, it's the same as a tree.

1+2*3^(4+1)+2/3 -> plus( plus(1, mul(2, power(3, plus(4,1)))), div (2/3)) would be the object hierarchy created.

OTOH if you are parsing it and doing the operations that can be done because all the operands are known:

1+2*3^(4+1)+2/3 -> 1+2*3^5+0.66 -> 1+2*243+0.66 -> 1+486+0.66 -> 487.66

You'd be, once again, doing the tree but instead of having it as an structure you'd be directly parsing the leafs than can be operated and act on them. This way would maybe be faster for simpler expressions (no need to construct the tree), but probably be more expensive than tree construction and resolution for more complex ones.

I'm absolutely stuck on your comment that trees are the wrong approach, or that trees are somehow incompatible with precedence. They encode the precedence more explicitly and unambiguously than the original string itself.

Trees being incompatible with precedence is like parentheses being incompatible with precedence.

>I'm absolutely stuck on your comment that trees are the wrong approach, or that trees are somehow incompatible with precedence. They encode the precedence more explicitly and unambiguously than the original string itself. Trees being incompatible with precedence is like parentheses being incompatible with precedence.

IMO, trees are not incompatible with precedence but I just prefer a more barebones approach to this fairly simple problem.

What's more barebones than a simple tree structure as used by essentially every compiler and interpreter, at least for one stage as an intermediate representation, out there today? (If they cover precedence, Forth implementations for instance don't care about it so don't need to use an AST even for an intermediate representation.)

Operators not only have precedence, but also associativity. Building a parser that works for arbitrary precedence and associativity is a standard school project that takes only a few lines more code than a parser that deals with operators with a single precedence level.

Here is an example in Haskell for operator parsing that uses nothing no more than the standard library: https://hackage-content.haskell.org/package/parser-combinato... Excluding comments it’s less than 50 lines of code, and it handles arbitrary precedence, prefix and postfix, ternary operators, infix operators with all three kinds of associativity.

Reply on news.ycombinator.com