How do you write an arithmetic expression parser i

问题:

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?

回答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).

回答2:

This is a simple parser with * over + precedence. I've tried to make it as educational as possible. I'll leave it up to you to add division and subtraction. Or brackets, if you're particularly ambitious.

function parse(str) {
    var signs = ["*", "+"];         // signs in the order in which they should be evaluated
    var funcs = [multiply, add];                 // the functions associated with the signs
    var tokens = str.split(/\b/);      // split the string into "tokens" (numbers or signs)
    for (var round = 0; round < signs.length; round++) {          // do this for every sign
        alert("tokens at this point: " + tokens.join(" "));
        for (var place = 0; place < tokens.length; place++) {    // do this for every token
            if (tokens[place] == signs[round]) {                         // a sign is found
                var a = parseInt(tokens[place - 1]);    // convert previous token to number
                var b = parseInt(tokens[place + 1]);        // convert next token to number
                var result = funcs[round](a, b);           // call the appropriate function
                alert("calculating: " + a + signs[round] + b + "=" + result);
                tokens[place - 1] = result.toString();      // store the result as a string
                tokens.splice(place--, 2);  // delete obsolete tokens and back up one place
            }
        }
    }
    return tokens[0];                  // at the end tokens[] has only one item: the result

    function multiply(x, y) {                   // the functions which actually do the math
        return x * y;
    }

    function add(x, y) {                        // the functions which actually do the math
        return x + y;
    }
}

var str = "25*5+5*7";
alert("result: " + str + " = " + parse(str));

回答3:

You can use the expression parser of math.js:

var str1= "25*5+5*7"
document.write(str1 + ' = ' + math.eval(str1)); 
// output: "25*5+5*7 = 160"

<script src="http://cdnjs.cloudflare.com/ajax/libs/mathjs/2.1.1/math.min.js"></script>

回答4:

You can create a new script:

function parse(str) {
  var s = document.createElement('script');
  s.text = "window.result = " + str;
  document.body.appendChild(s); // Run script
  document.body.removeChild(s); // Clean up
  return result;                // Return the result
}
document.body.innerHTML = parse("5*5+5*5");

Or use event handler content attributes:

function parse(str) {
  var el = document.createElement('div');
  el.setAttribute('onclick', "this.result = " + str);
  el.onclick();     // Run script
  return el.result; // Return the result
}
document.body.innerHTML = parse("5*5+5*5");

Note these approaches are unsafe and as evil as eval but uglier. So I don't recommend them.