반응형
문제
인프런 JS 알고리즘 강좌 문제를 한번 풀이해보겠습니다.
문제 해석
해당 문제는 스택을 이용한 풀이 문제입니다.
후위식 연산이란 연산자가 피연산자 뒤에 있는 표기식입니다.
예를 들어 중위표기식이 3+5*2 를 후위표기식으로 표현하면 352*+ 로 표현됩니다.
만약 다음과 같이 연산 최우선인 괄호가 표현된 식이라면 (3+5)*2 이면 35+2* 로 바꾸어야 합니다.
노트 메모
(끄적)
내 해답
function mySolution(s){
const stackNumber = [];
let result = -1;
for (let i of s) {
if (isNaN(i)) {
let a, b, op;
op = i;
if (result === -1) {
a = stackNumber.pop();
b = stackNumber.pop();
result = eval(`${a}${op}${b}`)
} else {
a = stackNumber.pop();
result = eval(`${result}${op}${a}`)
}
} else {
stackNumber.push(i)
}
}
return result;
}
let str="352+*9-";
console.log(mySolution(str)); // 12 출력
- 입력한 문자열에 대한 배열을 for 문을 돌면서 숫자인지 아닌지 판단합니다.
- 숫자면 Stack 에 push 합니다.
- 숫자가 아닌 문자(연산자)가 들어오면 Stack 에서 pop 을 한 숫자를 연산자를 통해 계산합니다.
이때 맨 처음 계산일 경우 pop 을 2번하여 숫자 2개를 꺼내어 계산하고, 이후에는 result 와 pop 한 숫자 1개를 꺼내서 계산합니다. - 해당 결과를 Result 에 저장합니다.
- Result 를 반환합니다.
인프런 해답
function solution(s){
let answer;
let stack=[];
for(let x of s){
if(!isNaN(x)) stack.push(Number(x));
else{
let rt=stack.pop();
let lt=stack.pop();
if(x==='+') stack.push(lt+rt);
else if(x==='-') stack.push(lt-rt);
else if(x==='*') stack.push(lt*rt);
else if(x==='/') stack.push(lt/rt);
}
}
answer=stack[0];
return answer;
}
let str="352+*9-";
console.log(solution(str));
let str="352+*9-";
console.log(solution(str)); // 12 출력
- 연산자가 아닌 숫자를 Stack 에 push 합니다.
- 숫자가 아니라면 Stack 에서 Pop 을 2번 수행합니다.
- 이때 먼저 pop 한 숫자를 rt 나중에 pop 한 숫자를 lt 로 변수를 할당합니다.
- 연산자에 맞게 계산하고 결과를 다시 Stack 에 push 합니다.
- 마지막에 stack[0] 만 남게 되는데 해당 값을 반환합니다.
마무리
해당 문제를 풀면서 eval 이라는 Javascript 함수를 알수 있었습니다.
(문자열에 연산자가 있으면 계산후에 반환해주는 함수)
또 Javascript에서 Stack 사용에 대해 이해할 수 있었습니다.
제가 알고리즘쪽 공부를 많이 해보지 않아서 조금 서툴지만 프론트엔드 개발자이긴 해도 알고리즘 공부를 해두면 좋을것 같아서 다시 공부를 시작하고 있습니다.
앞으로도 블로그에 꾸준히 알고리즘 관련 포스팅을 써볼 예정입니다.
반응형
'행사 및 개인 프로젝트 > 알고리즘 풀어보기' 카테고리의 다른 글
알고리즘 : 좌표 정렬 (sort 함수를 사용한 정렬 응용) (0) | 2023.03.21 |
---|---|
알고리즘 : 공주구하기 (인프런, 큐를 이용한 문제) (0) | 2023.03.01 |
백준 풀이 2750번 - 수 정렬하기 (+ 삽입정렬 개념) (0) | 2019.10.01 |