[알고리즘] 후위식 연산 스택(Stack)이용하여 풀기

후위식 연산

 

 

 

후위연산식이 주어지면 연산한 결과를 출력하는 프로그램을 작성하세요.
만약 3*(5+2)-9 을 후위연산식으로 표현하면 352+*9- 로 표현되며 그 결과는 12입니다.

 

 

 

 

입력설명

연산식의 길이는 50을 넘지않음

식은 1~9숫자와 +,-,*,/ 연산자로만 이루어짐

 

입력예제

352+*9-

 

출력예제

12

 

 

 

 

 

이 문제를 풀고나서 스택에 대해 조금은 감이 잡히는듯 싶다
처음엔 하나의 스택에 넣었다뺐다하면서 풀어나갈 알고리즘이 떠오르질않아서 
입력예제의 수와 연산식을 서로다른 스택에 담아서 다시 각각의 스택에서 꺼내와
for문을 돌고돌아 해결해가야하나..........하고 한참을 고민했다
그러다 하나의 스택을 갖고도 풀수 있는 방법을 알게되니
아 이런식으로 스택을 사용하는거구나 .. 하고
이제서야 조금씩 감이 오는듯하다

 

 

 

 

 

 

수도코드

1. 문자열로 들어온 인자를 배열로 만든다

2. 배열 요소를 탐색하면서 숫자일 경우 stack에 넣기

3. 배열 요소를 탐색하면서 연산기호일 경우 

    stack.pop()하여 right 변수에 담고

    stack.pop()하여 left 변수에 담아

    right 변수와 left 변수를 연산기호에 맞게 연산하여 다시 stack에 넣기

4. 최종적으로 stack에 남아있는 수 리턴

 

function solution(s){  
    let stack=[];

    s = s.split("");
    
    //기호가 오면 스텍[스텍.length-1] ,스텍[스텍.length-2] 팝하여 연산
   
    for(let i=0; i<s.length; i++){
      //숫자가 오면 스텍에 담기
      let nonum = Number.isNaN(Number(s[i]))
      if(!nonum){  //숫자면?
        stack.push(Number(s[i]));
      }else {  //기호면?
        let right = stack.pop();
        let left = stack.pop();
        if(s[i] === '+') stack.push(left+right);
        if(s[i] === '-') stack.push(left-right);
        if(s[i] === '*') stack.push(left*right);
        if(s[i] === '/') stack.push(left/right);
      }
    }


    return stack[0];
}

let str="352+*9-";
console.log(solution(str));