[leetcode] 150. Evaluate Reverse Polish Notation

Evaluate Reverse Polish Notation

You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation.

Evaluate the expression. Return an integer that represents the value of the expression.

Note that:

• The valid operators are '+', '-', '*', and '/'.
• Each operand may be an integer or another expression.
• The division between two integers always truncates toward zero.
• There will not be any division by zero.
• The input represents a valid arithmetic expression in a reverse polish notation.
• The answer and all the intermediate calculations can be represented in a 32-bit integer.

 

Example 1:

Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Example 2:

Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Example 3:

Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22
Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

 

Constraints:

• 1 <= tokens.length <= 104
• tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].

 

풀이 - 1

const operatorHandler: { [key: string]: Function } = {
  "+": (a: number, b: number): number => a + b,
  "-": (a: number, b: number): number => a - b,
  "*": (a: number, b: number): number => a * b,
  "/": (a: number, b: number): number => Math.trunc(a / b),
};

const operators: string[] = ["+", "-", "*", "/"];

function evalRPN(tokens: string[]): number {
  const arr: number[] = [];

  for (let i = 0; i < tokens.length; i++) {
    if (operators.includes(tokens[i])) {
      const b = arr.pop();
      const a = arr.pop();
      arr.push(operatorHandler[tokens[i]](a, b));
    } else {
      arr.push(Number(tokens[i]));
    }
  }

  return arr[0];
}

처음엔 콜백함수를 응용하면 될까 했는데 굳이 그러지 않고 해결할수 있을것 같았다.

handler와 operator를 선언하여 실제 로직 구현하는 스타일로 코드를 짜고 함수에서 사용하였다.

arr은 stack과 같이 사용하면서 연산자를 만났을때 연산하도록 구현했는데, 이방법은 스택 자료구조를 배우면서 한가지 예시로 역폴란드 표기법을 설명 들었던것이 떠올라 적용해보게 되었다.