js로 계산기를 만드는 중 한자리 숫자 뿐만 아니라 두자리수 이상의 사칙연산의 계산이 필요해서, 중위식을 컴퓨터 연산에 적합한 후위식으로 변환후 연산을 진행했다.
중위식(infix)
보편적으로 많이 쓴느 식, 숫자와 숫자 사이에 연산자가 위치
1 + 2 = 3
1 x 2 = 2
후위식(postfix)
숫자 사이에 연산자를 넣어주는 중위식과 달리 연산자가 뒤에 위치
1 2 + ==> 1 + 2
1 2 x ==> 1 x 2
중위식을 후위식으로 변환하기
자바스크립트의 배열을 스택으로 사용
- 규칙
- 숫자는 그대로 출력한다
- 연산자일경우 스택에 넣는다.
스택이 비어있을 경우
스택에 요소가 있을 경우연산자를 스택에 넣는다.최상단 연산자의 우선순위와 현재 연산자의 우선순위를 비교한다. 최상단 연산자의 우선순위가 현재 연산자의 우선순위보다 작을 경우 현재 연산자를 스택에 넣는다. (최상단 연산자 < 현재 연산자) 최상단 연산자의 우선순위가 현재 연산자의 우선순위보다 크거나 같은 경우 스택이 비거나 현재 연산자의 우선순위가 더 높을때까지 최상단 연산자를 스택에서 pop 하고 출력해준후 현재 연산자를 스택에 넣는다 (최상단 연산자 >= 현재 연산자) 우선순위 : 더하기 = 빼기 < 나누기 = 곱하기 - 스택이 빌 때까지 pop 하여 출력 해준다.
infixToPostfix() {
const infix = this.infix.split(' ');
const stack = [];
let postfix = '';
for (let item of infix) {
if (!isNaN(Number(item))) postfix += ` ${item} `;
else {
const lastOperation = stack[stack.length - 1];
while (
stack.length &&
this.operationPriority[lastOperation] >=
this.operationPriority[item]
) {
postfix += ' ' + stack.pop() + ' ';
}
stack.push(item);
}
}
while (stack.length) {
postfix += ' ' + stack.pop() + ' ';
}
return postfix.split(' ').filter(item => item !== '');
}후위식 표현 계산하기
자바스크립트의 배열을 스택으로 사용
- 규칙
- 숫자는 스택에 추가한다.
- 연산자 일경우 스택에서 숫자 두개를 뽑아준다.(pop 두번)
- 왼쪽 숫자는 첫번째 pop, 오른쪽 숫자는 두번째 pop 이며, 사칙연산후 다시 스택에 넣어준다.
computePostfix(postfix) {
const stack = [];
for (let item of postfix) {
if (!isNaN(Number(item))) stack.push(item);
else {
const rightNum = Number(stack.pop());
const leftNum = Number(stack.pop());
let newNum = 0;
switch (item) {
case '×':
newNum += leftNum * rightNum;
break;
case '÷':
newNum += leftNum / rightNum;
break;
case '+':
newNum += leftNum + rightNum;
break;
case '-':
newNum += leftNum - rightNum;
break;
}
stack.push(newNum);
newNum = 0;
}
}
return stack[0];
}