parsing - How do you write an arithmetic expression parser in JavaScript, without using eval or a constructor function?

Question

Given a string:

 var str1 = "25*5+5*7";

Without using eval or the constructor function in JavaScript, how would I be able to write a function called "output" that takes in the string and outputs the arithmetic value of the string, which in this case is 160?

Answer 1

Here's a full precedence expression evaluator following the recursive parsing idea I linked-to in a comment on the OP's question.

To do this, first I wrote a simple BNF grammar for the expressions I wanted to process:

sum =  product | sum "+" product | sum "-" product ;
product = term | product "*" term | product "/" term ;
term = "-" term | "(" sum ")" | number ;

This by itself requires a bit of experience to do simply and straightforwardly. If you have no experience with BNF you will find it incredibly useful for describing complex streams of items like expressions, messages, programming langauges, ...

Using that grammar, I followed the procedure outlined in the other message to produce the following code. It should be obvious that it is driven by grammar in a dumb mechanical way, and therefore pretty easy to write if you have that grammar.

(Untested. I'm not a JavaScript coder. This will surely contain a few syntax/semantic hiccups. Took me at about 15 minutes to code.)

var SE="Syntax Error";

function parse(str) { // returns integer expression result or SE
   var text=str;
   var scan=1;
   return parse_sum();

   function parse_sum() { 
      var number, number2;
      if (number=parse_product()==SE) return SE;
      while (true) {
        skip_blanks();
        if (match("+") {
           number2=parse_product();
           if (number2==SE) return SE;
           number+=number2;
        }
        else if (match('-')) {
                { number2=parse_product();
                  if (number2==SE) return SE;
                  number-=number2;
                } 
             else return number;
      }
   }

   function parse_product() {
      var number, number2;
      if (number=parse_number()==SE) return SE;
      while (true) {
        if (match("*") {
            number2=parse_term();
            if (number2==SE) return SE;
            number*=number2;
          }
          else if (match('/')) {
                  number2=parse_term();
                  if (number2==SE) return SE;
                  number/=number2;
               }
               else return number; 
      }
   }

   function parse_term() {
      var number;
      skip_blanks();
      if (match("(")) {
         number=parse_sum();
         if (number=SE) return SE;
         skip_blanks();
         if (!match(")") return SE;
      }
      else if match("-") {
              number= - parse_term();
           }
           else if (number=parse_number()==SE) return SE;
      return number;
   }

   function skip_blanks() {
      while (match(" ")) { };
      return;
    }

    function parse_number() {
       number=0;
       if (is_digit()) {
          while (is_digit()) {}
          return number;
        }
        else return SE;
    }

    var number;
    function is_digit() { // following 2 lines are likely wrong in detail but not intent
       if (text[scan]>="0" && text[scan]<="9") {
          number=number*10+text[scan].toInt();
          return true;
       }
       else return false;
    }

   function match(c) {
       if (text[scan]==c)
          { scan++; return true }
       else return false;
    }
 }

It is straightforward to code such parsers/evaluators. See my SO answer on how to build a parser (which links to how to how to build an evaluator).