Make a Scientific Calculator (Part 2)

In the last article, “Making a Scientific Calculator (I)”, we introduced the relevant theoretical knowledge about writing a mathematical calculator, mainly including prefix expression, infix expression, suffix expression and three kinds of expression calculation method and mutual transformation, but also introduced the complete scheduling field algorithm. In this article, we will implement a low-spec version of a calculator that supports only four simple operations.

Implementation approach

Define a class and define a set of operators in the constructor of the class
Each operator needs to have a priority and processing method attribute (no number of arguments is required, since this version only considers binary operators)
After defining the operator, we need to calculate a re to match the formula (used to judge the validity and read the formula).
Parse the formula to get the postfix expression
Calculate the postfix expression and get the formula

Code implementation

1. Code structure of Calculator class

class Calculation {
  constructor () {
    // Define a set of operators
    / /...
    // Compute the corresponding re
    this.calcReg()
  }

  // Regular computation
  calcReg () {}

  The /** * operator defines method *@param Symbol operator *@param Handle *@param Precedence Precedence **/
  definedOperator(symbol, handle,precedence) {}

  // The method to parse the passed expression
  parse(s) {}

  // Evaluate the resulting postfix expression
  evaluate(r){}

  // Other methods are also defined here
  //....

}
Copy the code

Above is the first version of the complete class code structure, through the implementation of each defined method can get a simple calculator, step by step to achieve the inside of the specific method.

2. Constructor

For a simple four-way operation, we need to define four operators +,-,*,/ and a pair of parentheses (,) in the constructor. The priority of multiplication and division is higher than that of addition and subtraction. For the brackets, the previous postfix expression transformation method can know, which left parenthesis goes straight to the operator stack, used to match right parenthesis delimited, and right parenthesis is not into the stack, left and right parentheses are not involved in operation at the same time, so they don’t need to specify the priority (can be set to 0 or less than the number of 0 to distinguish). So, here we set the priority of multiplication and division as 2, and the addition and subtraction as 1. Here is the constructor code:

  // define a _symbols property to store the definedOperator, which will be used later to implement definedOperator
  this._symbols = {}
  this.definedOperator("+".this.add,1)
  this.definedOperator("-".this.sub,1)
  this.definedOperator("*".this.multi,2)
  this.definedOperator("/".this.div,2)
  this.definedOperator("(")
  this.definedOperator(")")

  // Compute the re
  this.calcReg()
Copy the code

When defining the operator, we need to define several symbol handling functions as follows:

add(a,b) {
  return a + b
}

sub(a,b) {
  return a - b
}

multi(a,b) {
  return a * b
}

div(a,b) {
  return a / b
}
Copy the code

3. Operators define methodsdefinedOperator

This method does the following: saves the operator, saves the operator’s priority, and the processing method. So this method is relatively simple, the code implementation is as follows:

definedOperator(symbol, handle,precedence) {
  this._symbols[symbol] =  {
    symbol,handle,precedence
  }
}
Copy the code

4. Regular calculation methodcalcReg

When there are only four operations and the expression errors are not considered, the calculation of the re is relatively simple. The main rules are as follows:

Formulas can contain numbers and defined operators
Numbers can be decimals or whole numbers
Special operators (regular metacharacters) are escaped

calcReg () {
  let regstr =  "\\d+(? :\\.\\d+)? |" +
  Object.values(this._symbols).map(
    val= > val.symbol.replace(/[*+()]/g.'\ \ $&')
  ).join("|")
  this.pattern = new RegExp(regstr)
  console.log(this.pattern) // result: /\d+(? :\.\d+)? |\+|-|\*|/|\(|\)/g
}
Copy the code

Code explanation:

The first is to match the numbers\d+(? :\.\d+)?It could be integers, it could be decimals, so it could be 0 or it could be 1, and? :Indicates that the group is not captured
After removing the number, the other part should be in the corresponding defined operator, so just iterate through the operator, using|Connect, but+.*.(.)Regular metacharacters are special operators that need to be escaped.$&Represents a reference to a substring of the re match
Note: The final generated re needs to have the mode set togThat is, the global pattern, since the exec method of RegExp is used later, each match will start at the next location

5. Expression parsing and conversion methodsparsemethods

This method is the core method for implementing calculators, and is the method we explained earlier to convert infix expressions into postfix expressions. The implementation version considers four operations and does not consider the case of error handling, so the implementation of the algorithm is relatively simple. The specific implementation and code are explained as follows:

parse(s) {
  Operator stack, output stack
  let operators = [],result = [],
  // The result of the re match, the currently matched symbol
  match,token

  // remove whitespace processing
  s = s.replace(/\s/g.' ')
  // Resets the current position of the re
  this.pattern.lastIndex = 0
  do{
    match = this.pattern.exec(s)
    token = match ? match[0] : null
    // If no match is found, the match ends
    if(! token)break
    if(isNaN(+token)) { // If it is not a number
      if(token === "(") {// If it is an open parenthesis, it goes directly to the operator stack
        operators.push(token)
      } else if(token === ') ') {// When matching a close parenthesis
        // loop up the operator stack and push it into the output stack,
        // until an open parenthesis is encountered
        let o = operators.pop()
        while(o ! = ="(") {
          result.push(o)
          o = operators.pop()
        }
      } else if(! operators.length) {// The operator is empty and goes directly to the operator stack
        operators.push(token)
      } else {// Operator stack is not empty, need to compare priority
        // Get the previous operator
        let prev = operators[operators.length - 1]
        /** If the priority of the current operator is not higher than that of the top of the stack, the top of the stack is ejected and pushed onto the output stack, and the top of the stack is cyclically compared with the rest of the stack until the priority of the current element is higher than the top of the stack **/
        while(prev && this._symbols[token].precedence <= this._symbols[prev].precedence) {
          result.push(operators.pop())
          prev = operators[operators.length - 1]}// push the current operator onto the operator stack
        operators.push(token)
      }
    } else { // Token is a number that goes directly to the output stack
      result.push(+token)
    }
  } while(match)
  // Pop all remaining operators on the stack and push them onto the output stackresult.push(... operators.reverse())// Get the output stack, which is a postfix expression when converted to a string
  return result
}

Copy the code

The above is the implementation of the first version of the parse algorithm, let’s list an example to see how the results run

var calc = new Calculator();
console.log(calc.parse("1 + 2-3"))
console.log(calc.parse("2 * (4 - (2)"))
console.log(calc.parse("2 times 4-2 over 3 - (2 + 3) times 2"))
Copy the code

The running results are as follows:

By comparing the results obtained by the previous conversion algorithm, it is found that the results are consistent. So, for the time being, we think the algorithm is ok (actually there are problems)

6. Result calculationevaluatemethods

After operation result we can achieve the result calculation method, the basic idea is to explain in detail: in front of the scanning the postfix expression from beginning to end, digital output pressure into the stack, encountered symbols take out two Numbers (arithmetic) and symbols to participate in the operation results are then pushed to output the stack, finally will output the stack pop-up is the result. The implementation method is as follows:

evaluate(r){
  / / output stack
  let result = [], o = [];
  // Get the result of the current parse
  r = this.parse(r)
  for(let i = 0, len = r.length; i < len; i++) {
    let c = r[i]
    if(isNaN(c)) {
      let token = this._symbols[c] result.push(token.handle(... result.splice(-2)))}else {
      result.push(c)
    }
  }
  return result.pop();
}
Copy the code

Execute the following test code:

console.log(calc.evaluate("1 + 2-3"))
console.log(calc.evaluate("2 * (4 - (2)"))
console.log(calc.evaluate("2 times 4-2 over 3 - (2 + 3) times 2"))
Copy the code

The results are as follows, and the empirical results are correct.

conclusion

So far, we have implemented a basic calculator that supports four operations. If the given formula is normal, then there’s basically nothing wrong at this point. But let’s run the following tests

console.log(calc.evaluate("1+2-3abc"))
console.log(calc.evaluate(2 * (4-2) + ""))
console.log(calc.evaluate("2 times 4-2/3 - (2 + 3) times 2"))
Copy the code

You get the following results:

The reason is as follows: when we generate the re, we use the defined operators. All characters except numbers and operators will fail to match. For 1+2-3abc, when matching a, we execute if(! Token) break (1+2-3); For the second formula 2 * (4-2)+, there is an extra + at last. When participating in the operation, there is only one number left in the output stack, so the second number is read as undefined, and the sum is added to obtain the result NaN; The last expression is due to an extra open parenthesis, which does not define a function and therefore gives an error (theoretically the resulting stack should not contain the open parenthesis).

Therefore, our current implementation should have at least the following problems:

The parentheses are not strictly matched
Symbols other than numbers and defined operators are not processed
No extra operators are processed

In addition to the above issues, the current version does not support the following features:

An expression that contains a function
Prefixed unary operators such as plus and minus signs
Factorials and other postfix unary operators
Other operations, such as exponents, roots, logarithms, etc

In the next article we will address these issues and enrich our calculators to support more operations.

Make a Scientific Calculator (3)

Make a Scientific Calculator (Part 2)

Implementation approach

Code implementation

conclusion

Related Posts

Do not hold down to save pictures on the H5 mobile terminal

Use proxy to implement a more elegant VUE

JavaScript implements call, apply, and bind