후위 표기식2

문제

언어

  • JavaScript

순서도

  1. 간단한 스택 구현 또는 배열 사용
  2. 주어진 후위 표기식의 각 문자를 확인,
  3. 피연산자인 경우 스택에 push, 연산자인 경우 스택에서 적절히 pop 해서 연산 후 다시 스택에 push
  4. 스택에 들어있는 결과값 출력

문제 풀이 step 1

  • 이 문제를 풀기 전에 후위표기식의 특징부터 알아보겠습니다.
  • 수식을 표기하는 방법에는 전위, 중위, 후위의 3 가지 방법이 있습니다.
  • 이름 그대로 연산자가 피연산자 앞에 있으면 전위, 연산자가 피연산자 사이에 있으면 중위, 연산자가 피연산자 뒤에 있으면 후위입니다.
  • 사람은 보통 중위표기법을 사용하지만 컴파일러는 주로 후위표기법을 사용한다고 합니다.
  • 컴파일러가 후위표기법을 선호하는 이유는
    • 중위표기법에서는 먼저 계산하여야 할 부분을 나타내기 위하여 괄호를 사용해야 하는 반면, 후위표기법에서는 괄호가 필요 없습니다.
    • 즉, 중위표기법 (1+2)*7 의 경우 괄호는 더하기 연산이 곱하기 연산보다 먼저 수행되어야 함을 나타냅니다. 똑같은 식으 후위표기법으로 나타내면 12+7* 가 되어 괄호를 쓰지 않고서도 우선 계산하여야 할 내용을 나타낼 수 있습니다.
    • 그리고 연산자의 우선순위도 생각할 필요가 없습니다. 이미 식 자체에 우선순위가 표현되어 있기 때문입니다.
    • 후위표기법의 또 하나의 장점은 중위표기법의 경우 괄호가 존재해서 수식을 끝까지 읽은 후에 계산을 시작해야하는 반면, 후위표기법에서는 그럴 필요 없이 수식을 읽으면서 바로 계산을 해도 됩니다.

문제 풀이 step 2

  • 후위표기법의 특징을 토대로 어떤 방식으로 스택을 사용해서 후위표기식을 계산할 수 있을까요??
  • 먼저 수식을 왼쪽에서 오른쪽으로 스캔하여 피연산자이면 스택에 저장하고, 연산자이면 필요한 수만큼의 피연산자를 스택에서 꺼내 연산을 실행하고 연산의 결과를 다시 스택에 저장하면 됩니다.
  • 예를 들어 123*+45/- 의 경우,
    • 1 : 피연산자로 스택에 넣기 (Stack : [1])
    • 2 : 피연산자로 스택에 넣기 (Stack : [1, 2])
    • 3 : 피연산자로 스택에 넣기 (Stack : [1, 2, 3])
    • * : 연산자로 스택에서 최근 피연산자 꺼내서 연산 후 결과를 스택에 저장 (Stack : [1, 6])
    • + : 연산자로 스택에서 최근 피연산자 꺼내서 연산 후 결과를 스택에 저장 (Stack : [7])
    • 4 : 피연산자로 스택에 넣기 (Stack : [7, 4])
    • 5 : 피연산자로 스택에 넣기 (Stack : [7, 4, 5])
    • / : 연산자로 스택에서 최근 피연산자 꺼내서 연산 후 결과를 스택에 저장 (Stack : [7, 0.8])
    • - : 연산자로 스택에서 최근 피연산자 꺼내서 연산 후 결과를 스택에 저장 (Stack : [6.2])
  • 위와 같이 연산자와 피연산자를 구분해서 각 경우에 맞게 처리해주면 스택에는 계산의 결과값 하나만 남게 됩니다.
  • 그 값을 출력해주면 정답이 됩니다.
  • 추가 설명은 주석에 작성하겠습니다.

후기

  • Number.prototype.toFixed()
    • toFixed 메서드는 숫자를 고정 소수점 표기법으로 표기해 반환합니다.
    • 예를 들어, 
      console.log((123.456).toFixed(2)); // 123.45
console.log((0.004).toFixed(2)); // 0.00

Reference.

소스 코드

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

// 간단한 스택 구현
class Stack {
	constructor() {
		this.bucket = [];
		this.top = -1;
	}

	isEmpty() {
		return this.top === -1;
	}

	push(data) {
		this.bucket[++this.top] = data;
	}

	pop() {
		return this.bucket[this.top--];
	}
}

// 계산 함수 구현
const calculate = (stack, op) => {
	// 스택에서 피연산자 꺼내기
	const b = stack.pop();
	const a = stack.pop();
	let res = null;

	// 연산자에 맞게 계산
	if (op === "+") {
		res = a + b;
	} else if (op === "-") {
		res = a - b;
	} else if (op === "*") {
		res = a * b;
	} else if (op === "/") {
		res = a / b;
	}

	// 결과값 스택에 넣기
	stack.push(res);
};

const solution = (input) => {
	const n = Number(input[0]);
	const expression = input[1];
	const arr = input.slice(2).map(Number);

	const stack = new Stack();

	// 후위표기식을 왼쪽에서 오른쪽으로 스캔하며,
	for (let i = 0; i < expression.length; i++) {
		ch = expression[i];

		// 피연산자이면 스택에 넣기
		if (
			"A".charCodeAt(0) <= ch.charCodeAt(0) &&
			ch.charCodeAt(0) <= "Z".charCodeAt(0)
		) {
			stack.push(arr[ch.charCodeAt(0) - "A".charCodeAt(0)]);
			continue;
		}

		// 연산자면 계산하기
		calculate(stack, ch);
	}

	// 올바르게 계산이 이루어졌다면 스택에는 결과값 하나만 남았을 것이고, 그 값을 출력
	return stack.pop().toFixed(2);
};

console.log(solution(input));