[Java] SWEA 1223번 계산기2

SW Expert Academy

---

풀이

우선 후위 표기식으로 바꾸어주기 위해 스택을 사용하였습니다. 스택에 들어있는 연산자와 들어올 연산자를 비교하여 스택의 맨 위에 있는 연산자가 들어올 연산자보다 우선순위가 크거나 같다면 우선순위가 작아질때까지 스택에서 꺼내어 후위표기식에 추가하였습니다.

다음으로 후위 표기식을 연산할 때에는 스택의 맨 위에있는 숫자가 두 번째 피연산자가 되고 그 다음 숫자가 첫 번째 피연산자가 되게하여 해결하였습니다.

---

코드

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

public class Solution {
	public static char[] formula;
	public static int N;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder("");
		
		for (int tc = 1; tc <= 10; ++tc) {
			N = Integer.parseInt(br.readLine());
			String input = br.readLine();
			String formula = post(input);
			
			sb.append("#").append(tc).append(" ").append(calc(formula));
			System.out.println(sb);
			sb.setLength(0);
		}
	}
	
	public static char[] priority = new char[256];
	
	public static String post(String formula) {
		String postfix = "";
		Stack<Character> stk = new Stack<Character>();
		
		priority['*'] = 1;
		
		for (int i = 0; i < N; ++i)
	    {
	        if (formula.charAt(i) >= 48 && formula.charAt(i) <= 57) // 숫자일 경우
	        {
	            postfix += formula.charAt(i);
	        }
	        else // 연산자일 경우
	        {
	            if (!stk.empty())
	            {
	                while (priority[stk.peek()] >= priority[formula.charAt(i)])
	                {
	                    postfix += stk.pop();

	                    // stack이 비어버리면 while 조건문에서 검사를 진행할 수 없어 오류
	                    if (stk.empty())
	                    {
	                        break;
	                    }
	                }
	            }
	            stk.push(formula.charAt(i));
	        }
	    }

	    while (!stk.empty())
	    {
	        postfix += stk.pop();
	    }

	    return postfix;
	}
	
	public static int calc(String postfix)
	{
	    int result;
	    int len = postfix.length();

	    Stack<Integer> stk = new Stack<Integer>();
	    for (int i = 0; i < len; ++i)
	    {
	        if (postfix.charAt(i) >= 48 && postfix.charAt(i) <= 57)
	        {
	        	stk.push(postfix.charAt(i) - '0');
	        }
	        else
	        {
	            int y = stk.pop();
	            int x = stk.pop();

	            if (postfix.charAt(i) == '+')
	            {
	            	stk.push(x + y);
	            }
	            else if (postfix.charAt(i) == '*')
	            {
	            	stk.push(x * y);
	            }
	        }   
	    }

	    result = stk.pop();

	    return result;
	}
}

---

pyo7410/Algorithm