Algorithms and examples of parsing four arithmetic expressions in javascript_javascript skills

When writing code, we sometimes encounter situations where we need to parse four arithmetic expressions ourselves. This article briefly introduces the use of JavaScript to parse simple four arithmetic expressions.

1. Familiar concepts

Infix notation (or infix notation) is a general method of expressing arithmetic or logical formulas. The operator is in the middle of the operands in infix form (example: 3 4). That is, our most commonly used arithmetic expressions, infix expressions are easier for humans to understand, but not easy for computers to parse.

Reverse Polish notation (Reverse Polish notation, RPN, or reverse Polish notation) is a mathematical expression method introduced by Polish mathematician Jan Vukasiewicz in 1920. In reverse Polish notation, all operators are placed after the operands, so it is also called suffix notation. Reverse Polish notation does not require parentheses to indicate operator precedence. Reverse Polish notation makes it easy to use a stack structure to parse and calculate expressions. Therefore, here we parse four element expressions by first converting the infix expression into a reverse Polish expression. Then calculate the value.

2. Conversion process

Convert infix expression to postfix expression (scheduling field algorithm)

1. A mark pops up in the input queue
2. If the token is a number, add it to the output queue
3. If it is an operator (-*/), compare it with the operator on the top of the output stack. If the priority is less than or equal to the operator on the top of the stack, pop the operator on the top of the stack and add it to the output queue ( Loop until the above conditions are not met), and finally push this operator onto the stack.
4. If it is a left parenthesis, push it onto the stack
5. If it is a right parenthesis, continuously pop operators from the stack and add them to the output queue until the element at the top of the stack is the left parenthesis. Pop the left bracket and do not add it to the output queue. If no left parenthesis is found, it means that the parentheses in the original expression are not symmetrical and there is an error.
6. If the input queue is empty and there are still operators on the stack, if the operator on the top of the stack is a left parenthesis, it means that the original expression has unmatched parentheses. Pop the operators from the stack one by one and add them to the output queue.
7. Complete

3. Code conversion 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 prioraty(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. Evaluation of reverse Polish expression

1. Pop a token from the input queue
2. If it is an operand, add it to the output stack
3. If it is an operator, pop the two operands from the output stack and perform calculations, and push the calculated value onto the output stack.
4. Loop operation, if the input queue is empty and the output stack has only one number, this number is the result, otherwise there are redundant operands.

5. Calculation 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

Reverse Polish notation is not something you are used to when you first come into contact with it, but after you get familiar with it, you will find that the idea is actually very simple, unlike infix notation, which has various priorities and parentheses. Class, the logic is particularly troublesome, but the reverse Polish notation is more concise, there is no need to consider the priority at all, and there is no need for parentheses, square brackets and curly brackets to disrupt the situation.