I. Requirement + Final realization

Note: Front-end implementation only

1. The demand

The source of demand is a remote calculator made by a gay friend who does embedded C/C fuck. The requirement is to support the input of a string of four mixed formulas and return the computed result.

I would like to see how C/ CF wrapped JavaScript can achieve such a function. (I will discuss the two implementation ideas after the article, but also hope that you can put forward some optimization solutions and suggestions.)

2. Description: using the string (split, replace) and array (splice) method.

It mainly uses the method of splitting a string into an array, and the method of inserting and deleting an array, splice. The string regular replace method allows for user input habits that may vary, such as 1+2*3/4 versus 3 * 7 + 229.

Support:

    1. The basic four operations3 + 6 * 5/6-3;
    1. Four decimals3.14 + 6 * 5/6-3.5;
    1. High order four operations99 * 94-6.35 + 100/1024;
    1. Multiple four operations3 times 3 plus 3 times 16 minus 7 minus 5 plus 4/2 plus 22;
    1. The above general

Does not support:

    1. Operations with parentheses1 * (2-3);
    1. Other mathematical operations

3. Code implementation

/** * js four hybrid operation calculator function implementation (about 20 lines + noodle code) *@param {string} The four operation strings * of the STR input@return {number} The output is */
const calculator = (str) = > {
  // Define add character function
  const add = (arr, symbol) = > {
    let length = arr.length;
    while (length > 1) {
      arr.splice(length - 1.0, symbol); // Add the corresponding operator after each item
      length--;
    }
    return arr; // The object is to get an array of varying length
  }
  const array = add(str.replace(/\s*/g."").split('+'), '+').map(it= > add(it.split(The '-'), The '-').map(it= > add(it.split(The '*'), The '*').map(it= > add(it.split('/'), '/')))).flat(3);;
  // Multiply and divide first
  [The '*'.'/'].map(it= > {
    while (array.includes(it)) {
      const index = array.findIndex(o= > o === it);
      index > 0 && it === The '*' ? array.splice(index - 1.3, (Number(array[index - 1]) * Number(array[index + 1]))) : array.splice(index - 1.3, (Number(array[index - 1) /Number(array[index + 1))); }})// Perform addition and subtraction from left to right
  while (array.length > 1) {
    array[1= = ='+' ? array.splice(0.3, (Number(array[0]) + Number(array[2]))) : array.splice(0.3, (Number(array[0]) - Number(array[2))); }return Number(array[0]).toFixed(2);
}
Copy the code

If you are moderately familiar with ES6 syntax, you should be able to read the code easily. As you may have noticed, this is one of the things I struggle with: should I always write some spaghetti code as part of my daily development?

2, implementation steps (easy to understand the big man can jump to: step 3)

    1. Implement the most basic addition, subtraction, multiplication and division
    1. Supports high-digit operations
    1. Multiple operations are supported
    1. Support…

If you are a beginner, it is recommended to follow the process (or F12 verification + debugging), programming ability must be built in some way under the amount of code.

1. Version 1: basic addition, subtraction, multiplication and division

/ / version
const calculator = ((str) = > {
  // Define basic addition, subtraction, multiplication and division
  const add = (a, b) = > a + b;
  const sub = (a, b) = > a - b;
  const mul = (a, b) = > a * b;
  const div = (a, b) = > a / b;
  // Process the input string as an array
  const array = str.split(' ');
  // ** *
  [The '*'.'/'.'+'.The '-'].map(it= > {
    const index = array.findIndex(o= > o === it);
    if (index > 0) {
      switch (it) {
        case The '*':
          array[index + 1] = mul(array[index - 1], array[index + 1]);
          break;
        case '/':
          array[index + 1] = div(array[index - 1], array[index + 1]);
          break;
        case '+':
          array[index + 1] = add(Number(array[index - 1]), Number(array[index + 1]));
          break;
        case The '-':
          array[index + 1] = sub(Number(array[index - 1]), Number(array[index + 1]));
          break;
      }
      array.splice(index - 1.2)}})// return array[0];
  console.log('Return value :', array[0]); }) ('3 + 6 * 5/6-3')

// Return value: 5
Copy the code

This makes a calculator with four mixed operations!

But this calculator is very weak, only a most basic function of the implementation. That is, only one digit number can be added, subtracted, multiplied and divided.

So the first idea is to take advantage of the properties of arrays, and manipulate arrays to do four operations at a time. For array traversal, I give priority to * and /, followed by + and -. This is problematic, actually, method of priority in the actual operation was not obvious, is not how to influence the outcome of the operation (in the last version implementation involves the performance discussions will discuss), but the addition and subtraction will have an impact on: must be from left to right, or influence the outcome of the operation (there is not much redundancy).

【 Deal with the basic four operations 】

We first treat strings as arrays const array = str.split('');

Example of this step code:

(figure 1)

  1. You can see that when you’re working with strings'3 + 6 * 5/6-3'Deal with a['3', '+', '6', '*', '5', '/', '6', '-', '3'].
  2. And then in version one code, you can see that the order in which I’m doing the operations is[' * ', '/', '+', '-'], so the version of a support addition, subtraction, multiplication and division operation;
  3. const index = array.findIndex(o => o === it);This step finds the position of the symbol in the array in step 2.
  4. When you look at the processed array, symbols always appear one place apart, even if they are of higher priority*,/Method is also the result of the operation of the preceding and following terms at the position of the symbol.array[index + 1] = mul(array[index - 1], array[index + 1]);Change the value of the next item of the symbol to the operation result of calling the corresponding operation function;
  5. Delete sign bit and first item:array.splice(index - 1, 2)
  6. This is where you see the original definitionarrayThe array changes all the time. Take the printed result from node as an example (note the array of operations) :

(figure 2)You can see that each print prints the initial array and passesspliceMethod.

Disadvantages: This version does not support multiple operations, that is, four mixed operations can only be performed once. At the same time, it does not support high-order arithmetic.

2. Version 2: Implementation of high-digit operations

In Figure 1,If it is a numeric operation string involving high values (more than one digit), use it simplysplit('')The method processes a two-digit value into two items in an array, affecting the result of the operation.

So I need a method that, after receiving a string, gets the string I want:

(figure 3)

As shown in Figure 3, ary is needed.

So, the STR to ARY process in Figure 3 is what this release needs to do:

/** * implement the number of string partition *@param {string} STRS input string: '12*33/3+9+10' *@returns Array [' 12 ', '*', '33', '/', '3', '+', '9', '+', '10'] * /
const split = () = > {
  const result = str.split('+')  // the + is handled as an array
    .map(it= > {
      return it.split(The '-') // Encountered - processing as an array
        .map(it= > {
          return it.split(The '*') // The * is treated as an array
            .map(it= > {
              return it.split('/') // Encounters/as an array})})})return result.flat(3);
}
Copy the code

When I was designing this algorithm, I didn’t have a good idea at that time. This function handles the string as a multi-dimensional array, and then flattens the array. As shown in Figure 4:

(figure 4)

In Figure 4, we execute this function to get a multi-dimensional array (actually only a three-dimensional array at most), and the return value result prints the result that basically meets the desired array: [’31’, ‘+’, ’62’, ‘*’, ‘5’, ‘/’, ‘6’, ‘-‘, ‘3’].

Next, add the operator to it:

/** * defines the add character function *@param {string[]} Result Array ['31', '62*5/6-3'] *@param {string} Symbol The operator * passed in@returns Array ['31', '+', '62*5/6-3'] */
  const add = (result, symbol) = > {
    let length = result.length;
    while(length ! = =1) {
      result.splice(length - 1.0, symbol); // Add the corresponding operator after each item
      length--;
    }
    return result; // The object is to get an array of varying length
  }
Copy the code
  1. Such as the incoming[' and ', '62 * 5/6-3']You just have to fill in after the first term'+'Can.
  2. The goal of the implementation is to allow for multiple operations when for each because'+'Add operators to items in a partitioned array, so it’s used herewhileLoop statement, and is controlled by a variable length (this can also be done by iterating through arrays of numbers or arrays of for loops);
  3. Test results are shown in FIG. 5:

(figure 5)

This allows the arbitrary length of the numeric array to be typed and returned as a signed array.

【 Review 】 :

The above two functions are implemented as follows: split arrays by symbols, add symbols to arrays and symbols passed in:

Combine the two functions and simplify the code (actually, I prefer to write spaghetti code, but it may not be easy to read, but it looks better) :

  // Define add character function
  const add = (result, symbol) = > {
    let length = result.length;
    while(length ! = =1) {
      result.splice(length - 1.0, symbol); // Add the corresponding operator after each item
      length--;
    }
    return result; // The object is to get an array of varying length
  }
  const array = (strs = str) = >
    add(strs.split('+'), '+').map(it= >
      add(it.split(The '-'), The '-').map(it= >
        add(it.split(The '*'), The '*').map(it= >
          add(it.split('/'), '/')
        )
      )
    ).flat(3);
Copy the code

That is, any incoming operand string can be processed as the desired array as shown in Figure 6:

(figure 6)The array function then directly binds the return value of the inner handler.

For the above algorithm design if there is a better implementation also hope to have friends can point out that we can learn from each other.

3. Multiple operations are supported

Going back to version 1, the current implementation only supports a mix of four operations at a time. A more logical implementation would be to multiply and divide first, then add and subtract, and execute what comes first.

Complete operation code:

const calculator = (str) = > {
  const add = (result, symbol) = > {
    let length = result.length;
    while (length > 1) {
      result.splice(length - 1.0, symbol);
      length--;
    }
    return result;
  }
  const array = add(str.replace(/\s*/g."").split('+'), '+').map(it= > add(it.split(The '-'), The '-').map(it= > add(it.split(The '*'), The '*').map(it= > add(it.split('/'), '/')))).flat(3);;
  // Multiply and divide first
  while (array.includes(The '*') || array.includes('/')) {
    const itSymbol = array.find(o= > o === The '*' || o === '/');
    const index = array.findIndex(o= > o === The '*' || o === '/');
    index > 0 && itSymbol === The '*' ? array.splice(index - 1.3, (Number(array[index - 1]) * Number(array[index + 1]))) : array.splice(index - 1.3, (Number(array[index - 1) /Number(array[index + 1))); }// Perform addition and subtraction from left to right
  while (array.length > 1) {
    array[1= = ='+' ? array.splice(0.3, (Number(array[0]) + Number(array[2]))) : array.splice(0.3, (Number(array[0]) - Number(array[2))); }return Number(array[0]).toFixed(2);
}
Copy the code

Note: It is important to note that, because of personal habits, the input with whitespace is different, so we first use a regular expression str.replace(/\s*/g, “”) (whitespace is removed) before processing strings. Wait, what did I just think of?

If we are in the input time, consciously add a space to separate the operator and the value of the word ~ is not my previous version of the second string processing can save!!

So as a developer, we must pay attention to norms, norms, norms!

In the complete code above,

  1. Simplifies the call of addition, subtraction, multiplication and division functions, instead of usingArray.splice (index - 1, 3, operation)The operation can directly operate on two parameters.
  2. Once you have an array, multiply and divide, then add and subtract.
  3. In multiplication and division, you see if there is one* 或 /Two symbols, if they exist, locate the symbols and do each multiplication and division, mathematically speaking, which comes first (but I still stipulate that everything comes first)*And then compute all of them/This approach is the final implementation and is placed at the beginning of the article. Because when you actually do it, it doesn’t seem to matter what order you execute multiplication and division in, and for me, I feel like in this implementation,includes 与 findMultiple executions of the
  4. When all the multiplication and division methods are completed, there is only addition and subtraction left, this time in order to perform the addition and subtraction.
  5. And then we leave two decimal places.

In fact, this code is more mathematical thinking, the first operation of multiplication and division (who first operation), and then the operation of addition and subtraction.

If you have some other ideas, please discuss them together

Three, think

Back-end thinking:

1. Implement the inverse Polish expression

1+2*3 this is an infix expression, easily computed by the human brain, and the result is 7. Of course, computers can easily process this expression. When we type in 1.2+(-1+3*1)*2, the brain has to think about it a little bit, but the computer can still compute it quickly using a fixed code. However, when we randomly input the infix expression XXX, the human brain can calculate the result manually, but the computer cannot express a code block, so how can the computer achieve universal and fast calculation? The answer is postfix expressions. Infix and postfix expressions are involved in data structures, so I won’t talk about the concept, but let’s manually simulate the process of calculating string expressions on a computer.

2. Infix expression => suffix expression

What is easy for computers to calculate are suffixed expressions. The whole process is to convert known infix expressions into suffixed expressions.

2.1 Define [operand stack] and [operator stack] :

2.2 Operator stack out, operand stack in, the above formula can be: 123*+ this is a simple suffix expression

2.3 when computing postfix expressions, the operator stack reads * and the operand stack reads 2,3 to get the result 6. And then 1 plus 6 is 7.

3. More complex expression calculation
  • Into the stack:
    • (After the-Enter the operand stack as a negative number1.1-30);
    • Same as above, except that the operator stack is encountered(First go to the operator stack;

  • Until I met)

3.1 the use of#Symbols distinguish between negative numbers, high digits, and sign bits3.2 Therefore, the suffix expression is:# 1.1 # 3 # # # # * 10 + # 2 / #;

  • Unloading process:
    • The calculation did not encounter a sign bit#Prevail, take out in turn
    • Until the sign bit is encountered, three numbers are extracted1.1 3 to 10
    • When the symbol bit is encountered, the result stack is pushed out, and the symbol calculation result => result stack becomes30-1.1
    • Based on this calculation:

  • After the stack is removed, the evaluation of the inverse Polish expression is realized.

Front-end thinking:

When I got the requirement [to implement a calculator that supports four mixed operations], the first thing I thought was to convert a string to an array, and then to manipulate an array. However, because of the nature of high-level languages, many methods have been encapsulated, so it is relatively easy to implement.

Of course, you can also use the front-end code, with the backend thinking to achieve is also an option. Have a look at [portal]

The end of the

In fact, there is no difference between this calculator and the conventional calculator in the computer

  • implementation( 与 )Priority function;
  • Other math and so on…

To sum up, the back-end implementation is unbeatable in terms of performance, especially in terms of the speed of code execution. I don’t have the test data here, but if you have the ability to do so, you can look at the same algorithm. The space complexity of JS is several times that of C/C++ and other lower-level languages.

Similarly, if the C/C++ underlying language + back-end thinking to achieve [open up memory], transform infix expression into postfix expression defined [operand stack], [operator stack]; And all kinds of stack top stack bottom [pointer operation]; Plus if handed over to the user to use the Settings involved [proxy], network protocol encapsulation and so on… (The final total code quantity is hundreds of lines) I call it the business complexity (HHH) compared with the front-end 20 lines + code implementation ~ more things need to be considered in the bottom language, so the implementation cost is relatively more manpower, the same gain on computer performance cost performance is incomparable to front-end JS

Improper place still hope everybody corrects ~