← 10주차 · 스택 · 큐 · 덱
보통스택

후위 표기식 계산

후위 표기식이 토큰 배열 tokens로 주어져요. 각 토큰은 정수이거나 연산자 +, -, *, / 중 하나예요. 계산 결과를 정수로 반환해요.

후위 표기식은 연산자가 두 숫자 뒤에 와요. 예를 들어 2 1 + 3 *는 먼저 2 + 1을 하고 그 결과에 3을 곱해서 9가 돼요. 이 방식은 괄호가 없어도 계산 순서가 분명해요.

나눗셈은 몫만 남기고 0에 가까운 쪽으로 버려요. 예를 들어 -7을 2로 나누면 -3이에요.

예시

예시 1
입력
tokens = ["2", "1", "+", "3", "*"]
출력
9
설명
(2 + 1) * 3 = 9 예요.
예시 2
입력
tokens = ["4", "13", "5", "/", "+"]
출력
6
설명
13 / 5 = 2, 4 + 2 = 6 이에요.

제한 사항

  • 1 ≤ tokens.length ≤ 10,000
  • 정수는 -10,000 이상 10,000 이하예요.
  • 식은 항상 올바르고, 0으로 나누는 경우는 나오지 않아요.
숫자를 만나면 스택에 넣어요. 연산자를 만나면 스택에서 두 개를 꺼내는데, 먼저 꺼낸 값이 오른쪽 피연산자예요. 계산한 결과를 다시 스택에 넣어요. 다 처리하면 스택에 하나가 남고, 그게 답이에요.
javascript
function evalPostfix(tokens) {
  const stack = [];
  for (const token of tokens) {
    if (token === "+" || token === "-" || token === "*" || token === "/") {
      const b = stack.pop();
      const a = stack.pop();
      if (token === "+") stack.push(a + b);
      else if (token === "-") stack.push(a - b);
      else if (token === "*") stack.push(a * b);
      else {
        let q = Math.floor(Math.abs(a) / Math.abs(b));
        if ((a < 0) !== (b < 0)) q = -q;
        stack.push(q);
      }
    } else {
      stack.push(Number(token));
    }
  }
  return stack.pop();
}
이전 문제최근 K개의 이동 평균
다음 문제다음 큰 원소
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.