[SWEA-1223][스택] 계산기2 - Java

입력값으로 중위 표기식이 들어오면 이를 후위 표기식으로 바꾸고 계산하는 문제입니다.

스택을 이용해서 후위 표기식으로 바꾸고 계산까지 하면 됩니다.

괄호없이 덧셈과 곱셈만 있기 때문에 상대적으로 쉬운 문제랍니당.

 

import java.util.Scanner;
import java.util.Stack;

public class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = 10;

        for(int test_case = 1; test_case <= T; test_case++) {
            int N = Integer.parseInt(sc.nextLine());
            Stack<Character> s = new Stack<Character>();
            String line = sc.nextLine();
            String postfix = "";        //후위 표기식으로 바꾼 문자열

            for(int i =0 ;i<line.length(); i++) {
                if(line.charAt(i) != '+' && line.charAt(i) != '*') postfix += line.charAt(i);   //숫자인 경우 바로 넣어줌
                else {
                    if(line.charAt(i) == '*') {     //곱셈인 경우 스택에 바로 push
                        s.push(line.charAt(i));
                    }else {
                        do {                        //덧셈인 경우 자기보다 우선순위가 높은 *을 빼고 push
                            if(s.isEmpty()) break;
                            postfix+= s.pop();
                        }while(!s.isEmpty() &&s.peek()!= '+');
                        s.push(line.charAt(i));
                    }
                }
            }
            while(!s.isEmpty()) {
                postfix += s.pop();         //나머지 연산자
            }

            Stack<Integer> calc = new Stack<Integer>();
            for(int i =0; i<postfix.length(); i++) {
                if(postfix.charAt(i) != '+' && postfix.charAt(i) != '*')    //피연산자인 경우 push
                    calc.push(postfix.charAt(i) - '0'); 

                else {      //연산자가 나오면 맨 위의 두개를 빼서 계산후 push
                    int op1 = calc.pop();
                    int op2 = calc.pop();
                    char operator = postfix.charAt(i);
                    switch(operator) {
                        case '*':
                            int times = op1 * op2;
                            calc.push(times);
                            break;
                        case '+':
                            int plus = op1 + op2;
                            calc.push(plus);
                            break;
                    }
                }
            }

            System.out.println("#" + test_case + " " + calc.peek());
        }
    }
}

중위 표기식을 후위 표기식으로 바꿀 때는 연산자들을 stack에 넣었다 빼면서 만드는데, 연산자의 우선순위를 따져서 stack에 넣었다 뺐다 하면 됩니다.

 

새로 들어온 연산자의 우선순위가 stack에 들어 있는 친구의 우선순위보다 크면 바로 stack에 넣고,

작거나 같으면 걔를 빼고 넣습니다.

 

이해가 될랑가여....

 

암튼 이런 식으로 해서 후위 표기법으로 만들어 준 뒤, 또 stack을 활용해서 계산하면 됩니다.

피연산자(숫자)인 경우 stack에 push하고, 연산자인 경우 stack의 맨 위의 두 개를 뽑아서 계산하고 그 값을 다시 push하면 됩니다.

 

감사함다!!