This is the 11th day of my participation in the August More Text Challenge. For details, see:August is more challenging

Topic link

150. Evaluate the inverse Pollan expression

Topic describes

Evaluate the expression according to the inverse Polish notation.

Valid operators include +, -, *, and /. Each operand can be an integer or another inverse Polish expression.

Description:

  • Integer division preserves only the integer part.
  • A given inverse Polish expression is always valid. In other words, the expression always yields a valid value and there is no such thing as a zero divisor.

The test case

Input: tokens = [" 2 ", "1", "+", "3", "*"] output: 9: the formula into common infix arithmetic expression is: ((2 + 1) * 3) = 9Copy the code

Essential knowledge points

We are used to writing expressions as (1 + 2) * (3 + 4) with the addition, subtraction, multiplication and division operators in the middle, so we call them infix expressions.

The Polish expression is written as (* (+ 1 2) (+ 3 4)), with the operator first, and is therefore also called a prefix expression.

An inverse Polish expression is written as ((1, 2 +) (3, 4 +) *), with the operator written after it, and is therefore also known as a postfix expression.

For Polish and inverse Polish expressions, removing parentheses does not affect the priority calculation

The inverse Polish expression is calculated as follows:

You need to use a stack, stack, to do that

Iterate through each string of the test case from the beginning, and if the current character is a number, push it onto the stack. If the current character is not a number (that is, the operator), you need to perform two pop-up operations from the stack to get the numbers A and b, and then push the result of operator A of B into the stack. After the string is traversed, there is only one number left in the stack, the result of the operation

Subject analysis

There’s nothing to say, just follow the standard inverse Polish notation. If you run into a symbol, use the switch to select the corresponding symbol. The only detail is that the problem explicitly requires that the division be rounded to the decimal part

The topic answer

var evalRPN = function(tokens) {
	let stack = [];
	let oprator = new Set(['+'.The '-'.The '*'.'/']);
	tokens.forEach(n= > {
		if (oprator.has(n)) {
			let a = stack.pop(),
				b = stack.pop(),
				c;
			switch (n) {
				case '+':
					c = b + a;
					break;
				case The '-':
					c = b - a;
					break;
				case The '*':
					c = b * a;
					break;
				case '/':
					c = parseInt(b / a);
					break;
				default:
					break;
			}
			stack.push(c);
		} else {
			stack.push(Number(n)); }})return stack.pop();
};
Copy the code

A little optimization

Code looks very clear logic, is a little, EMMM, looking not very elegant subson

Change the switch to js Objec, and then change the key to js Objec, and then change the key to js Objec, and then change the key to JS Objec

var evalRPN = function(tokens) {
    let caculate = {
        '+': (b, a) = > a + b,
        The '-': (b, a) = > a - b,
        The '*': (b, a) = > a * b,
        '/': (b, a) = > parseInt(a / b)
    }
    let stack = [];
    let oprators = new Set([...Object.keys(caculate)]);
    tokens.forEach(n= > stack.push(oprators.has(n) ? caculate[n](stack.pop(), stack.pop()) : Number(n)));
    return stack.pop();
};
};
Copy the code

Take off