Simple Math Evaluator: Infix to Postfix Converter and calculator (Reverse polish notation)3/28/2016 A common way to express a mathematical expression is usually consisted by operators being placed between operands. For example: f(x) = 2 * 5 + 3  2 * (8 / (4 / 2)) + (3 * 3) This form of defining the expression is called Infix notation. As stated on wikpedia: Infix notation is the notation commonly used in arithmetical and logical formulae and statements. It is characterized by the placement of operators between operands – "infixed operators" – such as the plus sign in "2 + 2". Another way of defining the expression is called Reverse Polish notation (or commonly Postfix notation) where every operator follows all its operands. For example: 2 * 5 + 3  2 * (8 / (4 / 2)) + (3 * 3) equals to: 2 5 * 3 + 2 8 4 2 / / *  3 3 * + Notice that as long as every operator has a fix number of operands there's no need for parenthesis. Also it is more difficult to parse an Infix expression by computers than postfix. What I really like the most on Postfix notation is how nicely it fits the usage of Stack. This article shows how to convert a classic infix notation to the postfix notation so it can subsequently be evaluated by postfix math parser. Our JavaScript project consists of 3 modules:
..and main.js which just handles the modules. All of these can of course be found on GitHub repository. The algorithm for conversion the infix to postfix is very nicely described by Shuntingyard algorithm on the Wikipedia. Invented by famous Edsger Wybe Dijkstra. Very nice article can also be found on this page including the examples in Python. Generally speaking you iterate through the postfix tokens and perform a given task for a given operator, operand, parenthesis, function etc. An example from my simple JavaScript code: Each JavaScript module is responsible for a given task. The infix.js exposes a single method toPostfix() which takes only a single argument containing the infix expression. Common.js contains just a simple functions commonly used in the project and postfix.js is responsible for evaluating the postfix expression. One thing to mention from the JavaScript perspective is the following line: If you're not sure why exactly I use the not operator please check out my previous blog article explaining this topic. Plunker and GitHub
2 Comments
Justin Case
9/20/2018 10:56:39 am
Hi there. Thanks for the code. I would like to know how successive operators e.g 2+4, 5*/9 would be handled. I was thinking to do something when processOperator() is called in succession. A little help ??
Reply
Ivan Sivak
9/20/2018 12:08:50 pm
Hi Justin, thanks for your comment. I'm not exactly sure if you're pointing towards recognizing unary versus binary operators? Something like this: https://stackoverflow.com/questions/17254080/infixtopostfixalgorithmthattakescareofunaryoperators I think there are more places that should be updated in our code.. "processToken()" would probably require another "tokenType" such as "operatorUnary" and "operatorBinary" and then as you suggested "processOperator()"could maybe take this into account.. I only speculate here, comes quickly from my mind, however, yes, that could work if we would first of all start recognizing operator's type.
Reply
Leave a Reply. 
AboutBlog about my programming experiments, tests and so on. Categories
All
Archives
November 2016
