CODEWITHSUNDEEP
javascriptregexmatch
Jonathan Lam
Jonathan Lam

Reputation: 17351

"+" Quantifier not doing its job?

I'm a novice programmer making a simple calculator in JavaScript for a school project, and instead of using eval() to evaluate a string, I made my own function calculate(exp).

Essentially, my program uses order of operations (PEMDAS, or Parenthesis, Exponents, Multiplication/Division, Addition/Subtraction) to evaluate a string expression. One of my regex patterns is like so ("mdi" for multiplication/division):

mdi = /(-?\d+(\.\d+)?)([\*\/])(-?\d+(\.\d+)?)/g;    // line 36 on JSFiddle

What this does is:

I loop through this regular expression's matches with the following code:

while((res = mdi.exec(exp)) !== null) {    // line 69 on JSFiddle
    exp = exp.replace(mdi,
        function(match,$1,$3,$4,$5) {
            if($4 == "*")
                return parseFloat($1) * parseFloat($5);
            else
                return parseFloat($1) / parseFloat($5);
        });
    exp = exp.replace(doN,"");    // this gets rid of double negatives
}

However, this does not work all the time. It only works with numbers with an absolute value less than 10. I cannot do any operations on numbers like 24 and -5232000321, even though the regex should match it with the + quantifier. It works with small numbers, but crashes and uses up most of my CPU when the numbers are larger than 10.

For example, when the expression 5*.5 is inputted, 2.5 is outputted, but when you input 75*.5 and press enter, the program stops.

I'm not really sure what's happening here, because I can't locate the source of the error for some reason - nothing is showing up even though I have console.log() all over my code for debugging, but I think it is something wrong with this regex. What is happening?

The full code (so far) is here at JSFiddle.net, but please be aware that it may crash. If you have any other suggestions, please tell me as well.

Thanks for any help.

Upvotes: 2

Views: 131

Answers (3)

brainless coder
brainless coder

Reputation: 6430

Mathematical expression are not parsed and calculated with regular expressions because of the number of permutations and combinations available. The faster way so far, is POST FIX notation because other notations are not as fast as this one. As they mention on Wikipedia:

In comparison testing of reverse Polish notation with algebraic notation, reverse Polish has been found to lead to faster calculations, for two reasons. Because reverse Polish calculators do not need expressions to be parenthesized, fewer operations need to be entered to perform typical calculations. Additionally, users of reverse Polish calculators made fewer mistakes than for other types of calculator. Later research clarified that the increased speed from reverse Polish notation may be attributed to the smaller number of keystrokes needed to enter this notation, rather than to a smaller cognitive load on its users. However, anecdotal evidence suggests that reverse Polish notation is more difficult for users to learn than algebraic notation.

Full article: Reverse Polish Notation

And also here you can see other notations that are still far more better than regex.

Calculator Input Methods

I would therefore suggest you change your algorithm to a more efficient one, personally I would prefer POST FIX.

Upvotes: 1

DaoWen
DaoWen

Reputation: 33019

If you have any other suggestions, please tell me as well.

As pointed out in the comments, parsing your input by iteratively applying regular expressions is very ad-hoc. A better approach would be to actually construct a grammar for your input language and parse based on that. Here's an example grammar that basically matches your input language:

expr ::= term ( additiveOperator term )*
term ::= factor ( multiplicativeOperator factor )*
expr ::= number | '(' expr ')'

additiveOperator ::= '+' | '-'
multiplicativeOperator ::= '*' | '/'

The syntax here is pretty similar to regular expressions, where parenthesese denote groups, * denotes zero-or-more repetitions, and | denotes alternatives. The symbols enclosed in single quotes are literals, whereas everything else is symbolic. Note that this grammar doesn't handle unary operators (based on your post it sounds like you assume a single negative sign for negative numbers, which can be parsed by the number parser).

There are several parser-generator libraries for JavaScript, but I prefer combinator-style parsers where the parser is built functionally at runtime rather than having to run a separate tool to generate the code for your parer. Parsimmon is a nice combinator parser for JavaScript, and the API is pretty easy to wrap your head around.

A parser usually returns some sort of a tree data structure corresponding to the parsed syntax (i.e. an abstract syntax tree). You then traverse this data structure in order to calculate the value of the arithmetic expression.

I created a fiddle demonstrating parsing and evaluating of arithmetic expressions. I didn't integrate any of this into your existing calculator interface, but if you can understand how to use the parser

Upvotes: 1

Oriol
Oriol

Reputation: 288100

The problem is

bzp = /^.\d/;
while((res = bzp.exec(result)) !== null) {
  result = result.replace(bzp,
    function($match) {
      console.log($match + " -> 0 + " + $match);
      return "0" + $match;
    });
}

It keeps prepending zeros with no limit.

Removing that code it works well.

I have also cleaned your code, declared variables, and made it more maintainable: Demo

Upvotes: 1

Related Questions