[JAVA] SWEA 1224번 계산기3

문제

문자열로 이루어진 계산식이 주어질 때, 이 계산식을 후위 표기식으로 바꾸어 계산하는 프로그램을 작성하시오.

예를 들어

“3+(4+5)*6+7”

라는 문자열로 된 계산식을 후위 표기식으로 바꾸면 다음과 같다.

"345+6*+7+"

변환된 식을 계산하면 64를 얻을 수 있다.

문자열 계산식을 구성하는 연산자는 +, * 두 종류이며 문자열 중간에 괄호가 들어갈 수 있다.

이 때 괄호의 유효성 여부는 항상 옳은 경우만 주어진다.

피연산자인 숫자는 0 ~ 9의 정수만 주어진다.

입력

각 테스트 케이스의 첫 번째 줄에는 테스트 케이스의 길이가 주어진다. 그 다음 줄에 바로 테스트 케이스가 주어진다.

총 10개의 테스트 케이스가 주어진다.

출력

#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 답을 출력한다.

풀이

스택을 구현해 문제를 해결하였다.

 

입력을 char 형으로 받은 후, 루프를 돌며 괄호와 사칙연산에 대해 스택에 저장하여

 

후위 연산 표기법으로 만든 후,

 

사칙연산이 나오면 스택의 앞 두 수를 꺼내 연산하고 다시 스택에 넣도록 하였다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 계산기3 {
	
	public static int[] opStack = new int[10000];
	public static char[] stack = new char[10000];
	public static char[] calcs;
	public static int top;
	public static int opTop;
	public static int ans;
	
	public static String postCalc() {
		String postTmp = "";
		
		for (int i = 0; i < calcs.length; i++) {
			switch(calcs[i]) {
			case '(': 
				stack[++top] = calcs[i];
				break;
			case '+':
				while (stack[top] == '*' || stack[top] == '+') postTmp += stack[top--];
				stack[++top] = calcs[i];
				break;
			case '*':
				while (stack[top] == '*') postTmp += stack[top--];
				stack[++top] = calcs[i];
				break;
			case ')':
				while(stack[top] != '(') postTmp += stack[top--];
				top--;
				break;
			default:
				postTmp += calcs[i];
				break;
			}
		}
		
		return postTmp;
	}
	
	public static int Calc3(String postTmp) {
		for (int i = 0; i < postTmp.length(); i++) {
			char sth = postTmp.charAt(i);
			if (sth != '+' && sth != '*') opStack[++opTop] = sth - '0';
			else {
				int num2 = opStack[opTop--];
				int num1 = opStack[opTop--];
				
				if (sth == '+') opStack[++opTop] = num1 + num2;
				else if (sth == '*') opStack[++opTop] = num1 * num2;
			}
		}
		return opStack[opTop];
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		for (int test_case = 1; test_case <= 10; test_case++) {
			st = new StringTokenizer(br.readLine());
			int tc = Integer.parseInt(st.nextToken());
			calcs = new char[tc];
			top = -1;
			opTop = -1;
			calcs = br.readLine().toCharArray(); 
			
			System.out.println("#" + test_case + " " + (Calc3(postCalc())));
		}
	}
}