Inverse Polish expression evaluation

Answer:

  1. The inverse Polish expression is calculated by looking for the number to be calculated from left to right. When encountering an operator, the two adjacent numbers are taken out for corresponding calculation, and the calculation result is replaced by the original number and operator.

  2. Therefore, this is a first-in, last-out calculation, which can be solved using a stack:

    • traversetokens, and push the numbers to the stack.
    • If you encounter an operator, pull two numbers from the stack and evaluate them accordingly.
    • The order of the two elements in the formula, alwaysstack[stack.length - 2]In the former,stack[stack.length - 1]In the back.
    • Push the result to the stack and wait for the next calculation.
    • After all the calculations are done, there is only one element in the stack, which is the final result.
/ * * *@param {string[]} tokens
 * @return {number}* /
var evalRPN = function (tokens) {
  let stack = []; // Use a stack to store results

  // Iterate over the token from left to right, performing operations according to the symbol
  for (const token of tokens) {
    // When an operator is encountered, pop the top two elements on the stack and evaluate them accordingly
    if (token === '+' || token === The '-' || token === The '*' || token === '/') {
      // Pop up two elements that need to be converted to a number operation
      const num1 = Number(stack.pop());
      const num2 = Number(stack.pop());

      // Perform the corresponding operation and store the result on the stack, waiting for the next operation
      // Because of subtraction or division, the last element is evaluated as the minuend or dividend
      Num1 = num2; num1 = num1
      switch (token) {
        case '+':
          stack.push(num2 + num1);
          break;

        case The '-':
          stack.push(num2 - num1);
          break;

        case The '*':
          stack.push(num2 * num1);
          break;

        case '/':
          // Cache division quotient
          const quotient = num2 / num1;
          // Only integers can be used in the operation. Positive numbers are rounded down and negative numbers are rounded up
          stack.push(quotient > 0 ? Math.floor(quotient) : Math.ceil(quotient));
          break;

        default:
          break; }}else {
      // If it is a number, it is put on the stack and wait for calculationstack.push(token); }}// After the calculation, there is only one element in the stack, which is the final result
  return stack.pop();
};
Copy the code