[swexpert] Intermediate / Stack2 / 1222, 1223, 1224

🅰 1222. 계산기 1

​

✏️ 문제 풀이

중위표기식으로 작성된 문자열을 후위표기식으로 변경해 연산 값을 도출하는 문제이다.

연산자는 + 하나뿐이라 연산자의 우선순위를 고려할 필요가 없었다.

데이터를 문자열로 읽어와 후위표기식으로 변경해주었다.

후위식으로 변경할 때는 스택에 연산자만 들어가고, 후위표기법을 연산할 때에는 스택에 정수만 들어가기 때문에

Stack을 Char형태, Int 형태 2개로 선언한 후 문제를 풀었다.

char형식의 arr배열에 피연산자를 먼저 넣고, while문을 통해 Stack에 있는 연산자를 arr배열에 넣어주었다.

후위표기식 연산을 하기 위해 char형태로 저장되어 있는 정수들을 Character.getNumericValut(char a)를 통해 int형으로 변경해 주었으며, 연산을 수행했다.

​

✏️ 소스코드

package stack2;

import java.util.*;

public class Sw1222 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		for (int test_case = 1; test_case <= 10; test_case++) {
			Stack<Integer> opr = new Stack<>(); // 피연산자 저장 스택
			Stack<Character> opt = new Stack<>(); // 연산자 저장 스택
			
			int N = sc.nextInt();
			int a = 0;
			int op1, op2; // 피연산자 저장 변수
			String str = sc.next();
			char arr[] = new char[N];

			// 1-1.후위 표기식으로 변경
			for (int i = 0; i < N; i++) {
				char input = str.charAt(i);
				if (input == '+') {
					opt.push(input);
				} else {
					arr[a] = input;
					a++;
				}
			}
			// 1-2.연산자 input
			while (!(opt.isEmpty() == true)) {
				arr[a] = opt.pop();
				a++;
			}

			// 2-1.후위표기식 stack에 저장
			for (int i = 0; i < N; i++) {
				if (arr[i] != '+') {
					opr.push(Character.getNumericValue(arr[i]));
				} else {
					op1 = opr.pop();
					op2 = opr.pop();
					int result = op2 + op1;
					opr.push(result);
				}
			}
			System.out.printf("#%d %d%n", test_case, opr.pop());
	
		}
	}
}

} }

​

✅ 후기

​

문자열로 된 데이터를 어떻게 정수와 문자로 나눌지에 대해 고민을 많이 했었다.

(int) a, char a + '0', toString.charAt(index) 등 다양하게 시도해봤지만 아스키 코드가 나오거나, 0~9인 한자리 수만 int형으로 변경되었고 두자리수 넘어가면 제대로 변경되지 않았다. 그러던 중 Character wrapper 클래스의 getNumericValue메서드를 이용하니 숫자로 된 char형을 숫자형태 그대로 변경해주었다.

---

🅰 1223. 계산기 2

​

✏️ 문제 풀이

푸는 방식은 계산기 1과 비슷하였으나

연산자 stack에 쌓일 때 stack의 top에 *가 들어있고 +가 들어가려고 한다면 *가 +보다 입력 우선순위가 높으므로 pop()을 이용하여 *를 빼주고 후위표기법 배열인 op[]에 입력하여주고 +값을 stack에 push하였다.

후위표기법 연산 부분에 해줘야하는 연산이 2개로 늘어났으므로 삼항연산자를 이용하여 op[i] 가 * 이면 op2*op1 , +이면 op2+op1의 결과값을 피연산자 스택에 push 하여주었다.

이하 방법은 계산기 1번과 같다.

​

✏️ 소스코드

package stack2;

import java.util.*;

public class Sw1223 {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		for (int test_case = 1; test_case <= 10; test_case++) {

			Stack<Integer> opr = new Stack<>(); // 피연산자 저장 스택
			Stack<Character> opt = new Stack<>(); // 연산자 저장 스택
			int a = 0;
			int result;
			int N = sc.nextInt();
			String str = sc.next();
			char[] op = new char[N];

			// 1-1.후위표기식으로 변경
			for (int i = 0; i < N; i++) {
				char input = str.charAt(i);
				if (input == '+' || input == '*') {
					while (true) {
						if (input == '+') {
							if (!opt.isEmpty() && opt.peek() == '*') {
								op[a] = opt.pop();
								a++;
							} else {
								opt.push(input);
								break;
							}
						} else {
							opt.push(input);
							break;
						}
					}
				} else {
					op[a] = input;
					a++;
				}
			}
			// 1-2.연산자 input
			while (!opt.isEmpty()) {
				op[a] = opt.pop();
				a++;
			}

			// 후위 표기식 연산
			for (int i = 0; i < N; i++) {
				if (op[i] != '*' && op[i] != '+') {
					opr.push(Character.getNumericValue(op[i]));
				} else {
					int op1 = opr.pop();
					int op2 = opr.pop();
					result = (op[i] == '*' ? op2 * op1 : op2 + op1);
					opr.push(result);
				}
			}
			System.out.printf("#%d %d\n", test_case, opr.pop());
		}
	}
}
​

​

✅ 후기

​

계산기 1번을 풀어서 2번도 풀기 쉬웠다.

if (!opt.isEmpty() && opt.peek() == '*') 이 부분에서 !opt.isEmpty를 해주지 않으면

빈 스택의 peek()를 가져오기 때문에 스택 에러가 났었다.

---

🅰 1224. 계산기 3

​

✏️ 문제 풀이

(), *, /, -, + 모든 경우의 수를 계산하여 후위 연산자로 바꿔줘야 하는 문제이다.

스택 내 우선순위인 isp와 스택 외 우선순위인 icp를 전역변수(클래스변수)로 선언하였고, 연산자 데이터를 stack에 입력할 때 isp와 icp를 비교해서 넣어야 하므로 스택 top값의 isp를 구해오는 ispSearch함수를 구현하였다.

switch 함수를 이용하여 각각의 케이스를 생각하면서 코드를 구현하였다.

이하 과정은 계산기 2와 마찬가지로 풀었다.

​

✏️ 소스코드

package stack2;

import java.util.*;

public class Sw1224 {
	static int isp[] = { 0, 1, 2 };
	static int icp[] = { 3, 1, 2 };

	public static int ispSearch(char input) {
		if (input == '*' || input == '/') {
			return isp[2];
		} else if (input == '+' || input == '-') {
			return isp[1];
		} else if (input == '(') {
			return isp[0];
		}
		return -1; // 왜.... 붙여줘야 에러가 안나지...? 거짓일때의 return 값이 없어서 그런가...
	}

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		for (int test_case = 1; test_case <= 10; test_case++) {

			Stack<Integer> opr = new Stack<>(); // 피연산자 저장 스택
			Stack<Character> opt = new Stack<>(); // 연산자 저장 스택

			int N = sc.nextInt();
			String str = sc.next();
			char[] op = new char[N];
			int N1 = N;
			int a = 0;
			int result;

			// 1-1.후위표기식으로 변경
			for (int i = 0; i < N; i++) {
				char input = str.charAt(i);
				if (input == '*' || input == '/' || input == '+' || input == '-' || input == '(' || input == ')') {
					switch (input) {
					case '(':
						opt.push(input);
						break;
					case '*':
						if (!opt.isEmpty() && icp[2] > ispSearch(opt.peek())) {
							opt.push(input);
						} else {
							while (true) {
								if (!opt.isEmpty() && icp[2] <= ispSearch(opt.peek())) {
									op[a] = opt.pop();
									a++;
								} else {
									opt.push(input);
									break;
								}
							}
						}
						break;
					case '/':
						if (!opt.isEmpty() && icp[2] > ispSearch(opt.peek())) {
							opt.push(input);
						} else {
							while (true) {
								if (!opt.isEmpty() && icp[2] <= ispSearch(opt.peek())) {
									op[a] = opt.pop();
									a++;
								} else {
									opt.push(input);
									break;
								}
							}
						}
						break;

					case '+':
						if (!opt.isEmpty() && icp[1] > ispSearch(opt.peek())) {
							opt.push(input);
						} else {
							while (true) {
								if (!opt.isEmpty() && icp[1] <= ispSearch(opt.peek())) {
									op[a] = opt.pop();
									a++;
								} else {
									opt.push(input);
									break;
								}
							}
						}
						break;
					case '-':
						if (!opt.isEmpty() && icp[1] > ispSearch(opt.peek())) {
							opt.push(input);
						} else {
							while (true) {
								if (!opt.isEmpty() && icp[1] <= ispSearch(opt.peek())) {
									op[a] = opt.pop();
									a++;
								} else {
									opt.push(input);
									break;
								}
							}
						}
						break;
					case ')':
						while (true) {
							if (opt.peek() == '(') {
								opt.pop();
								N1 -= 2;
								break;
							} else {
								op[a] = opt.pop();
								a++;
							}
						}
						break;
					}
				} else {
					op[a] = input;
					a++;
				}
			}
			// 1-2.연산자 input
			while (!opt.isEmpty()) {
				op[a] = opt.pop();
				a++;
			}

			// 2.후위표기법 연산
		
			for (int i = 0; i < N1; i++) {
				if (op[i] != '*' && op[i] != '/' && op[i] != '-' && op[i] != '+') {
					opr.push(Character.getNumericValue(op[i]));
				} else {
					int op1 = opr.pop();
					int op2 = opr.pop();
					switch (op[i]) {
					case '*':
						result = op2 * op1;
						opr.push(result);
						break;
					case '/':
						result = op2 / op1;
						opr.push(result);
						break;
					case '+':
						result = op2 + op1;
						opr.push(result);
						break;
					case '-':
						result = op2 - op1;
						opr.push(result);
						break;
					}
				}
			}
			System.out.printf("#%d %d%n", test_case, opr.pop());
		}
	}
}

​

✅ 후기

​

후위표기법으로 구현하는 방법은 할만했으나, 후위표기법으로 된 연산의 값을 구하는 과정에서 결과값이 자꾸 -1이 나와서

확인해보니 주어진 문자열의 길이와 ()가 사라진 후위표기법으로 구현된 문자열의 길이가 달라서 발생한 문제였다.

그래서 괄호가 스택에서 빠질때 마다 N-=2를 해줘서 후위표기법의 문자열의 길이를 구하여 계산하였다.

​