[JAVA][SW Expert Academy] 1223. 계산기2

 

 [SW Expert Academy] 1223. 계산기2

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

 

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14nnAaAFACFAYD&categoryId=AV14nnAaAFACFAYD&categoryType=CODE

SW Expert Academy

---

 문제 내용

문자열로 이루어진 계산식이 주어질 때, 이 계산식을 후위 표기식으로 바꾸어 계산하는 프로그램을 작성하시오. 예를 들어 “3+4+5*6+7” 라는 문자열로 된 계산식을 후위 표기식으로 바꾸면 다음과 같다. "34+56*+7+" 변환된 식을 계산하면 44를 얻을 수 있다. 문자열 계산식을 구성하는 연산자는 +, * 두 종류이며 피연산자인 숫자는 0 ~ 9의 정수만 주어진다. [입력] 각 테스트 케이스의 첫 번째 줄에는 테스트 케이스의 길이가 주어진다. 그 다음 줄에 바로 테스트 케이스가 주어진다. 총 10개의 테스트 케이스가 주어진다. [출력] #부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 답을 출력한다.

 

 

 해결 순서

1. 후위표기식 : 연산자를 피연산자 뒤에 표기하는 표기식
2. 중위표기식 → 후위표기식 변환 방법

  > 연산자는 스택에 push

  > 피연산자는 그대로 출력

  > 현재 연산자보다 우선순위가 낮은 top을 만날 때 까지 pop

  > 현재 연산자보다 우선순위가 낮은 top인 경우 현재 연산자 push

  > 동일 우선순위의 연산자가 들어오면 top 연산자는 pop

  > 더이상 연산자가 없으면 스택에 있는 피연산자 전체 출력

  > 스택이 비어있으면 변환 종료

3. 후위표기식 연산 방법
  > 피연산자는 스택에 push

  > 연산자 차례에는 스택에 들어있는 피연산자를 pop하여 순서를 바꿔 연산 후 연산 결과를 다시 push

    (ex. + 연산 -> top = 2 일 때 pop / top = 3 일 때 pop 하여 3 + 2 = 5 -> push 5) 

4. 연산자 우선순위 주의

  > * 또는 / 연산자는 + 나 - 연산자보다 우선순위가 높다.

 

 

 

 문제 풀이

import java.util.Stack;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Solution
{
    static int result;
    static String strPostfix;
    static Stack<String> stack;
    public static void main(String args[]) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = 10;
        
        for(int test_case = 1; test_case <= T; test_case++)
        {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int strLen = Integer.parseInt(st.nextToken());
            result = 0;
            strPostfix = "";
            stack = new Stack<>();
            String str = br.readLine();
 
            for (int i = 0; i < str.length(); i++) {
                postfix(Character.toString(str.charAt(i)));    
            }
            
            while (!stack.isEmpty()) {
                strPostfix += stack.pop();
            }
 
            for (int i = 0; i < strPostfix.length(); i++) {
                cal(Character.toString(strPostfix.charAt(i)));
            }
            
            System.out.println("#" + test_case + " " + result);
        }
    }
 
    public static void postfix(String s) {
        if (strPostfix.equals("")) {
            strPostfix = s;
        } else {
            if (s.equals("+")) {
                if (stack.isEmpty()) {
                    stack.push(s);
                } else {
                    while (!stack.isEmpty()) {
                        strPostfix += stack.pop();
                    }
                    stack.push(s);
                }
            } else if (s.equals("*")) {
                if (stack.isEmpty()) {
                    stack.push(s);
                } else {
                    while (!stack.isEmpty()) {
                        if (stack.peek().equals("*")) {
                            strPostfix += stack.pop();
                        } else {
                            break;
                        }
                    }
                    stack.push(s);
                }
            } else {
                strPostfix += s;
            }
        }
    }
    
    public static void cal(String s) {
        int a = 0, b = 0;
        
        if (s.equals("+")) {
            a = Integer.parseInt(stack.pop());
            b = Integer.parseInt(stack.pop());
            result = b + a;
            stack.push(String.valueOf(result));
        } else if (s.equals("*")) {
            a = Integer.parseInt(stack.pop());
            b = Integer.parseInt(stack.pop());
            result = b * a;
            stack.push(String.valueOf(result));
        } else {
            stack.push(s);
        }
    }
}