Talk:Parsing/RPN to infix conversion: Difference between revisions

:::: I added an extra example, now sadly all the tasks are wrong (although I think a couple already address this). The task already requires the RPN and infix to be the same. One thing, I can't find the template that says (globally) the task changed. So I'll have to mark them all incorrect if I can't find one. --[[User:Dgamey|Dgamey]] 16:49, 17 December 2011 (UTC)

::::: I added {{tmpl|clarified-review}} for you. –[[User:Dkf|Donal Fellows]] 19:06, 17 December 2011 (UTC)

:: Huh, if you want minimum parentheses and follow the [[wp:Associativity|actual definition]] of associativity, the task itself is incorrect: - and / are non-associative. The term "left-associative" is often loosely used when parsing infix notations, to determine the order of ops in absence of parens, but to do the reverse and requiring minimum number of parens, this kind of definition of associativity is not enough, and you need to know the exact behaviour of the operators (a + b + c requires none, but a - b - c may need one pair, even though both + and - are both loosely "left associative"). The task needs some more work, or there may be other holes after people try to fix the solutions. --[[User:Ledrug|Ledrug]] 17:50, 17 December 2011 (UTC)

::: I didn't write it, I just noticed it was broken. Perhaps it should be knocked back to draft. --[[User:Dgamey|Dgamey]] 18:20, 17 December 2011 (UTC)

:::: The RPN code shouldn't try to use commutativity, as that causes problems in situations where there are side-effects. (OK, not in ''this'' example, but in general.) While a few languages allow optimizers to use it (notably [[C]] and [[C++]]), most don't because it causes much confusion; overall, language designers have found it better to be more predictable than that (where side-effects are present at all, of course). –[[User:Dkf|Donal Fellows]] 18:59, 17 December 2011 (UTC)

:::: Hmm? I didn't say anything about commutativity. It has nothing to do with this task. What's of concern is the execution order of operators, that is, given some arbitrary operator *, if <code>a * b * c</code> needs parentheses to be unambiguous. If * is associative (in the strict sense), <code>(a * b) * c = a * (b * c) = a * b * c</code>, and no parens are really required; commutativity is completely independent of this. Subtraction "-" is not commutative, while exclusive-or "xor" is, but neither is associative. It wouldn't have mattered had there not been the (rather pointless) "minimal parens" requirement, but as it is, some clarification is needed as to what constitutes "minimal". Currently for example the Tcl code would convert <code>1 2 3 + +</code> into <code>1 + (2 + 3)</code>, which is fine by me--but I'm normally not the one who demands the output to match some random standard to the last letter. --[[User:Ledrug|Ledrug]] 20:51, 17 December 2011 (UTC)

: Tcl version is now fixed (it would have helped if the original example had been sensitive to such things, but there you go). –[[User:Dkf|Donal Fellows]] 18:59, 17 December 2011 (UTC)