Click here to Skip to main content
11,488,877 members (78,352 online)
Click here to Skip to main content

JavaScript Mathematical Expression Evaluator

, 18 Nov 2008 Public Domain 85.3K 1.7K 47
Rate this:
Please Sign up or sign in to vote.
A mathematical expression evaluator in pure JavaScript, with support for user defined variables.

Introduction

There are a number of good articles in CodeProject on this subject. This one, however, presents the same thing in pure JavaScript. Although this expression evaluator does not come close to some of those which have been written in C#, C++, or VB, I am sure it can be useful to those who want to learn the concepts behind expression parsing and subsequent evaluation.

Basic Concepts

Before we go into the details, let's understand a few terms first:

  • Infix notation is a common arithmetic and logical formula notation, in which the operators are written in infix-style, i.e., between the operands they act on. The major problem with this notation is that it is not that simple to parse, by a computer, as prefix or postfix notations. In infix notation, unlike the prefix or postfix notations, the parentheses surrounding the groups of operands and operators are necessary to indicate the intended order in which the operations are to be performed. In the absence of parentheses, certain precedence rules determine the order of operations.
  • Postfix notation, also known as Reverse Polish notation (RPN), is an arithmetic formula notation, derived from the Polish notation introduced in 1920 by the Polish mathematician Jan Lukasiewicz. RPN was invented by an Australian philosopher and computer scientist Charles Hamblin in the mid-1950s, to enable zero-address memory stores. As a user interface for calculation, the notation was first used in Hewlett-Packard's desktop calculators in the late 1960s, and then in the HP-35 handheld scientific calculator launched in 1972. In RPN, the operands precede the operator, thus dispensing the need for parentheses. Why is this notation more suitable to computers? The implementations of RPN are stack-based; that is, operands are popped from a stack, and calculation results are pushed back into it. Although this concept may seem obscure at first, RPN has the advantage of being extremely easy, and therefore fast, for a computer to analyze. Let's look at the practical implications of RPN:
    • Calculations proceed from left to right.
    • There are no brackets or parentheses, as they are unnecessary.
    • Operands precede operator, they are removed as the operation is evaluated.
    • When an operation is done, the result becomes an operand itself (for later operators).
    • There is no hidden state, and no need to worry about whether you have hit an operator or not.

Examples

The calculation, ((5 - 2) * 4) / 3, can be written down like this in RPN:

5 2 - 4 * 3 /

The expression is evaluated in the following way (the stack is displayed after the operation has taken place):

Input Stack Operation
5 5 Push operand
2 5, 2 Push operand
- 3 Subtract top two operands
4 3, 4 Push operand
* 12 Multiply top two operands
3 12, 3 Push operand
/ 4 Divide the top two operands

The final result, 4, lies on the top of the stack at the end of the calculation.

Converting from Infix Notation

Edsger Dijkstra invented an algorithm named "shunting yard", which converts from infix notation to RPN. The shunting yard algorithm is also stack-based.

  • While there are tokens to be read:
    • Read a token.
      • If the token is a number, then add it to the output queue.
      • If the token is a function token, then push it onto the stack.
      • If the token is a function argument separator (e.g., a comma):
        • Until the topmost element of the stack is a left parenthesis, pop the element onto the output queue. If no left parentheses are encountered, then either the separator was misplaced or the parentheses were mismatched.
      • If the token is an operator, O1, then:
        • while there is an operator O2 at the top of the stack, and either
          • O1 is left-associative and its precedence is less than or equal to that of O2, or
          • O1 is right-associative and its precedence is less than that of O2,
        • pop O2 off the stack, onto the output queue;
        • push O1 onto the operator stack.
      • If the token is a left parenthesis, then push it onto the stack.
      • If the token is a right parenthesis, then pop the operators off the stack, onto the output queue, until the token at the top of the stack is a left parenthesis, at which point it is popped off the stack but not added to the output queue. At this point, if the token at the top of the stack is a function token, pop it too onto the output queue. If the stack runs out without finding a left parenthesis, then there are mismatched parentheses.
  • When there are no more tokens to be read, pop all the tokens, if any, off the stack, add each to the output as it is popped out, and exit. (These must be operators; if a left parenthesis is popped, then there are mismatched parentheses.)

Tokenizer

The tokanizer.js file contains the code to break the expression into various tokens. This is very much important as we get the expression in string form. Breaking this string into tokens helps in subsequent parsing and conversion. Once the tokenizer completes, we are left with an array of tokens, which is then fed to the infix2postfix converter. The tokenizer makes use of the switch clause to distinguish the common operators and the string constants.

Stack

The stack data structure is implemented in the Stack.js file. This data structure is implemented using an array. For the purpose of debugging, the stack also provides a toString method which basically converts the stack into a comma separated string.

Evaluator

The entire expression conversion and evaluation logic is written in the Evaluator.js file. The root object is called Expression, which exposes two methods, namely:

  • ParseExpression: To convert an infix expression into an equivalent postfix expression.
  • EVal: Which actually evaluates the postfix expression. This method internally makes a call to ParseExpression, if the expression is not already parsed.

Like the tokenizer, the evaluator also makes use of the switch clause to distinguish between the various operators. The most important part of this code is the default case handler in the EVal() method and the Parse() function. The evaluator also makes use of an excellent piece of code written by Mr. Matt Kruse for handling the date data type. The rest of the code in this file simply contains some helper functions. The user defined variables can be added using the AddVar(varName, varValue) method on the Expression object. Similarly, the user defined variables can be cleared using the ClearVars() method. The following table summarizes the various operators and functions supported by the expression evaluator:

Arithmetic Logical Comparison Functions
+ ! = AVG
- & > ABS
* | < ACOS
/   <= ASC
%   >= ASIN
^   <> ATAN
      CDATE
      CHR
      COS
      DATE
      FIX
      HEX
      IIF
      LCASE
      LEFT
      LOG
      MAX
      MID
      MIN
      RIGHT
      ROUND
      SIN
      SQRT
      TAN
      UCASE

License

This code is released under the GPL variant. Please see License.txt for more details.

History

  • October 31st, 2005 - Initial release.
  • November 04th, 2005 - Added licensing details.
  • May 26th, 2006 - Fixed a small bug pointed out by Mr. Raphael Wils.
  • June 21st, 2006 - Updated the JavaScript and sample page to demonstrate variable support.
  • November 17th, 2008 - Fixed the small bug pointed out by CodeProject member Zephirim. Also added the reference section containing the links to reference documents pointed out by Zephirim.

References

License

This article, along with any associated source code and files, is licensed under A Public Domain dedication

Share

About the Author

Prasad Khandekar
Software Developer (Senior) Freelancer
India India
I am a software professional with over 20 years of commercial business applications design and development experience.

My programming experience includes Java, Spring, .NET, Classic VB & ASP, Scripting, Power Builder, PHP, Magic & far far ago FoxPro, C, Assembly and COBOL.

From last 11 years I am mostly working with Java Technology. I am currently available to take up new assignments.

Comments and Discussions

 
Questionbug for calc this ((MAX(3,2)-MIN(3,2))/MIN(3,2))*100 Pin
Member 1170998121-May-15 22:02
memberMember 1170998121-May-15 22:02 
QuestionGreat educational tool! Pin
jeremy leach23-Mar-13 19:02
memberjeremy leach23-Mar-13 19:02 
QuestionIs it possible to add "&&" and "||" functions? Pin
ws_chef14-Jan-11 7:25
memberws_chef14-Jan-11 7:25 
QuestionPossible Bug Pin
Zephirim13-Nov-08 14:29
memberZephirim13-Nov-08 14:29 
AnswerRe: Possible Bug Pin
Prasad Khandekar17-Nov-08 0:05
memberPrasad Khandekar17-Nov-08 0:05 
GeneralRPN History Pin
Zephirim12-Nov-08 14:52
memberZephirim12-Nov-08 14:52 
GeneralRe: RPN History Pin
Prasad Khandekar16-Nov-08 23:30
memberPrasad Khandekar16-Nov-08 23:30 
GeneralIIF function Pin
ramin_v8025-Jul-08 8:16
memberramin_v8025-Jul-08 8:16 
GeneralRe: IIF function Pin
Prasad Khandekar6-Aug-08 21:48
memberPrasad Khandekar6-Aug-08 21:48 
GeneralIIF function Pin
rjayaabharathi@gmail.com4-Aug-09 20:58
memberrjayaabharathi@gmail.com4-Aug-09 20:58 
GeneralUse of variables Pin
Mungi22-Jan-08 20:57
memberMungi22-Jan-08 20:57 
AnswerRe: Use of variables Pin
Prasad Khandekar28-Jan-08 3:54
memberPrasad Khandekar28-Jan-08 3:54 
GeneralThanks Pin
guyinfun7-Feb-07 7:24
memberguyinfun7-Feb-07 7:24 
GeneralBug Report 2 Pin
BladeXX25-Sep-06 21:50
memberBladeXX25-Sep-06 21:50 
GeneralBug Report [modified] Pin
BladeXX25-Sep-06 5:52
memberBladeXX25-Sep-06 5:52 
GeneralRe: Bug Report Pin
Member 246648229-May-08 19:29
memberMember 246648229-May-08 19:29 
GeneralPlease help me to try the following expression with Evaluator.js Pin
Gopalakrishnan B R16-Jun-06 2:03
memberGopalakrishnan B R16-Jun-06 2:03 
AnswerRe: Please help me to try the following expression with Evaluator.js Pin
Prasad Khandekar21-Jun-06 4:07
memberPrasad Khandekar21-Jun-06 4:07 
Generalbug report Pin
Raphael Wils25-May-06 0:47
memberRaphael Wils25-May-06 0:47 
AnswerRe: bug report Pin
Prasad Khandekar26-May-06 0:10
memberPrasad Khandekar26-May-06 0:10 
GeneralWhat's wrong with eval() Pin
Jaroslaw Kowalski31-Oct-05 4:36
memberJaroslaw Kowalski31-Oct-05 4:36 
GeneralRe: What's wrong with eval() Pin
Kochise31-Oct-05 4:49
memberKochise31-Oct-05 4:49 
GeneralRe: What's wrong with eval() Pin
Prasad Khandekar2-Nov-05 19:32
memberPrasad Khandekar2-Nov-05 19:32 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.150520.1 | Last Updated 18 Nov 2008
Article Copyright 2005 by Prasad Khandekar
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid