When writing code, we sometimes encounter situations where we need to parse the four arithmetic expressions by ourselves. This article briefly introduces the use of JavaScript to implement the parsing of simple four arithmetic expressions.
1. Familiar with the concept
Infix notation (or infix notation) is a general arithmetic or logical formula representation method. The operator is in the middle of the operand in the form of an infix (example: 3 + 4). That is, we use the most commonly used arithmetic expressions. Infix expressions are easier for humans to understand, but are not easy for computer analysis.
Reverse Polish notation (RPN, or inverse Polish notation) is a mathematical expression method introduced by the Polish mathematician Jan Vukasevich in 1920. In the inverse Polish notation, all operators are placed behind the operand, so it is also called the suffix notation. Inverse Polish notation does not require brackets to identify operator priority. The inverse Polish notation is easy to use a stack structure to parse and calculate the expression, so here we parse the four element expressions, which first converts from the infix expression to the inverse Polish expression. Then calculate the value.
2. Conversion process
Convert an infix expression to a suffix expression (scheduling field algorithm)
1. Enter the queue and pop up a mark
2. If the mark is a number, add it to the output queue
3. If it is an operator (+-*/), compare it with the operator at the top of the stack in the output stack. If the priority is less than or equal to the operator at the top of the stack, pop up the operator at the top of the stack and add it to the output queue (loop until the above conditions are not met), and finally push the operator onto the stack.
4. If it is a left bracket, push it into the stack
5. If it is a close bracket, the operator is constantly popped out from the stack and added to the output queue, and know that the element at the top of the stack is the left bracket. The left bracket pops up and does not add the output queue. If no left bracket is found, it means that the brackets in the original expression are asymmetric and there is an error.
6. If the input queue is empty and there are still operators in the stack, if the operator at the top of the stack is left bracket, it means that the original expression has mismatched brackets. Pop up the operators in the stack one by one and add them to the output queue.
7. Completed
3. Convert code implementation
function isOperator(value){var operatorString = "+-*/()";return operatorString.indexOf(value) > -1}function getPrioraty(value){switch(value){case '+':case '-':return 1;case '*':case '/':return 2;default:return 0;}}function priority(o1, o2){return getPrioraty(o1) <= getPrioraty(o2);}function dal2Rpn(exp){var inputStack = [];var outputStack = [];var outputQueue = [];for(var i = 0, len = exp.length; i < len; i++){var cur = exp[i];if(cur != ' ' ){inputStack.push(cur);}}console.log('step one'); while(inputStack.length > 0){var cur = inputStack.shift();if(isOperator(cur)){if(cur == '('){outputStack.push(cur);}else if(cur == ')'){var po = outputStack.pop(); while(po != '(' && outputStack.length > 0){outputQueue.push(po);po = outputStack.pop();}if(po != '('){throw "error: unmatched()";}}else{while(prioraty(cur, outputStack[outputStack.length - 1]) && outputStack.length > 0){outputQueue.push(outputStack.pop());}outputStack.push(cur);}}else{outputQueue.push(new Number(cur));}}console.log('step two');if(outputStack.length > 0){if(outputStack[outputStack.length - 1] == ')' || outputStack[outputStack.length - 1] == '('){throw "error: unmatched ()";}while(outputStack.length > 0){outputQueue.push(outputStack.pop());}}console.log('step three');return outputQueue;}console.log(dal2Rpn('1 + 2'));console.log(dal2Rpn('1 + 2 + 3'));console.log(dal2Rpn('1 + 2 * 3'));console.log(dal2Rpn('1 + 2 * 3 - 4 / 5'));console.log(dal2Rpn('( 1 + 2 )'));console.log(dal2Rpn('( 1 + 2 ) * ( 3 - 4 ) / 5'));console.log(dal2Rpn('( 1 + 2 ) * (( 3 - 4 ) / 5)'));4. Inverse Polish expression evaluation
1. Pop up a mark from the input queue
2. If it is an operand, add it to the output stack
3. If it is an operator, pop two operands from the output stack and calculate, and push the calculated value into the output stack.
4. Loop operation. If the input queue is empty and there is only one number on the output stack, this number is the result, otherwise there will be an unnecessary operand.
5. Calculate the code
function evalRpn(rpnQueue){var outputStack = [];while(rpnQueue.length > 0){var cur = rpnQueue.shift();if(!isOperator(cur)){outputStack.push(cur);}else{if(outputStack.length < 2){throw "unvalid stack length";}var sec = outputStack.pop();var fir = outputStack.pop();outputStack.push(getResult(fir, sec, cur));}}if(outputStack.length != 1){throw "unvalid expression";}else{return outputStack[0];}}6. Conclusion
The inverse Polish representation is not used to it when you first come into contact with it, but after getting familiar with it, you will find that the idea is actually very simple, unlike the infix representation, which has various priorities, and there are brackets, which are particularly troublesome logic. The inverse Polish representation is relatively concise, and there is no need to consider priority at all, and there is no need to use brackets, and brackets and braces to disrupt the situation.