[SWEA] JAVA - 1223 계산기2

중위표기법을 후위표기법으로 바꾼다음 계산 결과를 출력하는 문제입니다. 분명 이번주에 배웠는데 중위표기법을 후위표기법으로 바꾸는 부분이 잘 떠오르지 않아 구글링해가며 로직을 다시 이해했습니다. 이 문제에서는 '+', '*' 연산자만 나오기 때문에 연산자 우선순위를 간단하게 비교할수 있습니다.

 

먼저 중위표기법을 후위표기법으로 바꿀때, 피연산자를 만나면 후위표기법 리스트에 저장합니다. 만약 연산자가 들어온다면 이 연산자가 입력값(연산자)과 우선순위를 비교하여 우선순위가 높은 연산자를 pop해준뒤 다음 새로운 연산자를 스택에 넣어줍니다.

 

그 다음으로 연산자 스택에 쌓여있는 값들을 모두 후위표기법 리스트에 붙여줍니다.

 

마지막으로 후위표기법으로 표시된 리스트에서 연산작업을 해줍니다. 아래와 같이 동작합니다.

 

1. 피연산자를 만나면 스택에 push
2. 연산자를 만나면 필요한만큼(2개)의 피연산자를 스택에서 pop, 연산결과를 다시 스택에 push
3. 수식이 끝나면 마지막으로 스택을 pop하여 출력

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Stack;
 
public class Solution {
    static Stack<Character> midStack;
    static Stack<Integer> postfixStack;
    //입력값 우선순위가 더 높으면 true
    //낮거나 같으면 false
    public static boolean check(char input, char top) {
        if(input == '*' && top != '*') return true;
        else if(input == '+' && top == '*') return false;
        else return false;
    }
     
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
         
        for (int t = 1; t <= 10; t++) {
            int N = Integer.parseInt(br.readLine());
             
             
            char[] mid = new char[N];
            char[] result = new char[N];
            midStack = new Stack<>();
            mid = br.readLine().toCharArray();
            int idx = 0;
            //중위표기식 후위표기식으로 변환
            for (int i = 0; i < N; i++) {
                if(mid[i] != '+' && mid[i] != '*') { //피연산자일때
                    result[idx++] = mid[i];
                     
                }else {
                    if(midStack.empty()) {
                        midStack.push(mid[i]);
                    }else {
                        if(!check(mid[i], midStack.peek())) {
                            result[idx++] = midStack.pop();
                            midStack.push(mid[i]);
                        }else {
                            midStack.push(mid[i]);
                        }   
                    }
                }
            }
            while(!midStack.empty()) {
                result[idx++] = midStack.pop();
            }
             
             
            //후위표기식 계산
            postfixStack = new Stack<>();
            for (int i = 0; i < result.length; i++) {
                if(result[i] != '*' && result[i] != '+') {
                    postfixStack.push(result[i]-'0');
                }else {
                    int r = postfixStack.pop();
                    int l = postfixStack.pop();
                    if(result[i] == '*') {
                        postfixStack.push(r*l);
                    }else {
                        postfixStack.push(r+l);
                    }
                }
            }
            sb.append("#").append(t).append(" ").append(postfixStack.pop()).append("\n");
             
        }
        System.out.print(sb);
    }
 
}

 

간단 풀이

문제에서 연산자가 '*', '+' 연산자 밖에 없고 우선순위도 곱하기 연산이 높기 때문에 먼저 곱하기 연산을 모두 해준다음 나머지 연산을 해주는 풀이를 친구에게 배웠습니다!!! 이 과정에서 곱하기 연산결과를 다시 스택에 넣고, 남은 더하기 연산을 모두 해줍니다.

 

공유를 허락해주신 같은반 친구!! 경섭님 감사합니다 :)

package com.java.algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Stack;

public class SWEA_1223_계산기2 {
	static Stack<Character> midStack;
	static Stack<Integer> postfixStack;
	//입력값 우선순위가 더 높으면 true
	//낮거나 같으면 false
	public static boolean check(char input, char top) {
		if(input == '*' && top != '*') return true;
		else if(input == '+' && top == '*') return false;
		else return false;
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		for (int t = 1; t <= 10; t++) {
			int N = Integer.parseInt(br.readLine());
			
			
			char[] mid = new char[N];
			char[] result = new char[N];
			midStack = new Stack<>();
			mid = br.readLine().toCharArray();
			int idx = 0;
			//중위표기식 후위표기식으로 변환
			for (int i = 0; i < N; i++) {
				if(mid[i] != '+' && mid[i] != '*') { //피연산자일때
					result[idx++] = mid[i];
					
				}else {
					if(midStack.empty()) {
						midStack.push(mid[i]);
					}else {
						if(!check(mid[i], midStack.peek())) {
							result[idx++] = midStack.pop();
							midStack.push(mid[i]);
						}else {
							midStack.push(mid[i]);
						}	
					}
				}
			}
			while(!midStack.empty()) {
				result[idx++] = midStack.pop();
			}
			
			
			//후위표기식 계산
			postfixStack = new Stack<>();
			for (int i = 0; i < result.length; i++) {
				if(result[i] != '*' && result[i] != '+') {
					postfixStack.push(result[i]-'0');
				}else {
					int r = postfixStack.pop();
					int l = postfixStack.pop();
					if(result[i] == '*') {
						postfixStack.push(r*l);
					}else {
						postfixStack.push(r+l);
					}
				}
			}
			sb.append("#").append(t).append(" ").append(postfixStack.pop()).append("\n");
			
		}
		System.out.print(sb);
	}

}