3

I am attempting to implement a shunting-yard algorithm for a calculator following the rules laid out in https://en.wikipedia.org/wiki/Shunting-yard_algorithm .

When programming the unary minus, however, I do not know which precedence method to follow due to the ideas raised in following question https://math.stackexchange.com/questions/1299236/why-does-unary-minus-operator-sometimes-take-precedence-over-exponentiation-and

As this is a key component of a functioning calculator, which precedence is the 'industry standard' and is there an algorithm which would perform both of these precedence methods at the same time to solve this problem?

Bonus points if the algorithm (if it exists) retains the O(n) linear time increase.

  • If I understand what you are saying, you want to parse the expression first according to a grammar that has unary - lower precedence than binary ^, and second, also parse the expression according to a grammar where unary - is higher precedence than binary ^, and still be O(n). Well, that is easy, you just parse it twice because O(2n) = O(n). – Erik Eidt Sep 4 '16 at 0:30
2

When looking for an "industry standard", one might look at the most popular programming languages. However, the problem you are describing occurs only in conjunction with the exponentiation operator. And languages like C, C++, Java, C# these languages don't have this operator, Javascript currently does not have one, but this is going to change (see below).

In most languages which have an exponentiation operator like PHP and Python and others, according to this source, the exp operator is defined to have a higher precedence than unary operators. The article mentions also a few exceptions like shell programming in Bash. The same source tells us the upcoming Javascript/ECMAScript version 2016 (ES7) will introduce the ** operator in Javascript, but ambigouus usage will be forbidden.

Note that "higher precedence" of the exp operator here only means "it binds more tightly to the left side" of the exp operator as described in the Python docs. An unary minus on the right side will be always applied first, but that is simply because the minus sign in such a case is next to the second argument, and the exponentiation sign isn't, so it is not really a matter of precedence (see one of the answers from the Math.SE question you gave a link to).

So I guess using the Python/PHP rules would be fine and not astonish anyone, but this is not mandatory, and if you think a different convention would serve you better, pick that.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.