스택 응용 문제
괄호 쌍 맞추기
문제
- pop된 왼쪽 괄호와 바로 읽었던 오른쪽 괄호가 같은 종류이면 다음 괄호를 읽음
- 괄호의 종류 - [ ]. { }. ( )
- 모든 괄호를 읽은 뒤 에러가 없고 스택이 empty이면 괄호들이 정상적으로 사용된 것 -> true 출력
- 만일 모든 괄호를 처리한 후 스택이 empty가 아니면 짝이 맞지 않는 괄호가 스택에 남은 것으로 실패 -> false 출력
문제풀이
// String으로 괄호를 한 번에 입력 받음
// 입력 받은 문자열을 char로 변환하여 처음 입력된 순서대로 push하고
// peek()으로 반환된 top이 그 다음 스택에 들어 갈 char과 짝이 맞는지 확인함
// 짝이라면 그 괄호 쌍은 출력되고 다음 char과 top을 대조함
// 짝이 아니라면 스택에 push
package question;
import implement.linkedlistStack.ListStack;
// 괄호 쌍 맞추기 문제
public class pairOfParentheses {
public static void main (String arg[]) {
System.out.println(resoultion("[(){()}]"));
System.out.println(resoultion("[({}[]){}]"));
System.out.println(resoultion("{(){())}"));
}
public static boolean resoultion(String s){
ListStack<Character> stack = new ListStack<Character>();
for(int i = 0; i < s.length(); i++){
char ch = s.charAt(i);
if(!stack.isEmpty()){
if(stack.peek()=='{' && ch=='}' ){
System.out.print(stack.pop());
System.out.print(ch);
}else if(stack.peek() == '(' && ch == ')'){
System.out.print(stack.pop());
System.out.print(ch);
}else if(stack.peek() == '[' && ch == ']'){
System.out.print(stack.pop());
System.out.print(ch);
}else{
stack.push(ch);
}
}
else{
stack.push(ch);
}
} // for문
if(stack.isEmpty()) return true;
else return false;
}
}
결과
입력값
1) "[(){()}]"
2) "[({}[]){}]"
3) "{(){())}"
차례대로 1, 2, 3의 입력의 결과이다.
3은 stack에 값이 남아 false를 출력한다.
회문 검사하기
문제
회문 - 앞으로부터 읽으나 뒤로부터 읽으나 동일한 스트링
주어진 문자열이 회문인지 검사하는 프로그램을 작성하여라.
문제풀이
1) 입력된 문자열을 char으로 바꾸어 전반부 문자들을 스택에 push한다.
2) 후반부의 각 문자를 차례로 pop한 문자와 비교한다.
2-1) 만약 문자열이 홀수라면 가운데 문자를 버리고 진행한다.
3) 마지막 문자까지 동일하고 스택이 empty가 되면 이 문자열은 회문이다.
public static boolean check(String str) {
ListStack<Character> stack = new ListStack<Character>();
// 전반부 입력값 스택에 push
for(int i = 0; i < str.length()/2; i++){
stack.push(str.charAt(i));
}
// 입력값의 길이가 홀수라면 중간값은 버림
//// 전반부 입력값의 top과 후반부 입력값을 비교
for(int j = (str.length()%2!=0)? (str.length()/2+1):(str.length()/2);
j < str.length(); j ++){
//비교하여 같다면 pop
if(stack.peek().equals(str.charAt(j))) stack.pop();
else break; // 다르면 더 이상 안 읽어도 회문 아님이 확정!!
}
if(stack.isEmpty()) return true;
else return false;
}
}str의 입력 길이가 홀수이면 후반부 for문의 j는 가운데 값 다음부터 시작하여 가운데 문자를 버렸다.
해결된 문제점
for(int i = 0; i < str.length()/2; i++){
stack.push(str.charAt(i));
}
for(int j = str.length()/2; j < str.length(); j ++){
//비교하여 같다면 pop
if(stack.peek().equals(str.charAt(j))) stack.pop();
}홀짝을 고려하지 않고 코드를 이렇게 짜더라도 잘 돌아가는 것처럼 보인다.
if문의 조건에 맞지않으면 그냥 버려지기 때문에 홀수 길이 입력 시 가운데 값이 걸러진다.
하지만 같은 문자열로 홀수 길이를 입력하면 가운데 값이 버려지지 않고 첫번째 a와 짝지어지기 때문에 마지막 a가 남아 오류를 발생한다.
입력 길이가 홀수일때 따로 처리 방법을 여러 가지 생각해보았다.
(후에 else문도 추가하였다!)
for(int i = 0; i < str.length()/2; i++){
stack.push(str.charAt(i));
}
// 입력값의 길이가 홀수라면 중간값은 버림
if(str.length()%2!=0) stack.pop();
//// 전반부 입력값의 top과 후반부 입력값을 비교
for(int j = str.length()/2; j < str.length(); j ++){
//비교하여 같다면 pop
if(stack.peek().equals(str.charAt(j))) stack.pop();
else break; // 다르면 더 이상 안 읽어도 회문 아님이 확정!!
}처음엔 전반부와 후반부 사이에 입력 길이가 홀수라면 pop을 이용하여 가운데 값을 버리려고 하였으나, 가운데 값은 후반부의 for문이 처음 돌 때 str.charAt(str.length()/2)에 있다!
첫번째 for문과 두번째 for문의 str.length()/2을 (str.length()/2)+1로 바꾸면 입력 길이가 짝수일때 문제가 생긴다. 그래서 두번째 for문의 j값을 홀짝에 맞춰 다르게 설정하였다. 홀수 일 때 int j = str.length()/2+1)가 되어 가운데 값은 읽히지 않게 된다.
후위표기법 수식 계산
문제
중위표기법 : A+BC-D
후위표기법(postfix notation) : ABC+D-
후위표기법 수식은 괄호 없이 중위표기법 수식을 표현할 수 있어 컴파일러는 중위표기법을 후위표기법으로 바꾸어 이를 스택을 이용해 계산한다.
후위표기법 수식을 계산하는 프로그램을 작성하여라.
문제풀이
1) 수식을 입력 받는다.
2) 입력 받은 수식 문자열을 한 글자씩 불러온다.
3) 입력값이 피연산자이면 stack에 push한다.
4) 입력값이 연산자라면 pop을 두번한다.
4-1) 두번째 pop된 값과 첫번째 pop된 수를 연산자를 통해 계산하고 다시 stack에 push한다.
5) 모든 입력값에 대해 2~4를 반복한다.
6) 마지막으로 pop한 값이 계산 결과이다.
함수 소스코드
public static int calculator(String str) {
ListStack<Integer> stack = new ListStack<Integer>();
for(int i = 0; i < str.length(); i++){
char input = str.charAt(i);
if(Character.isDigit(input)) { // 숫자 즉, 피연사라면 push
stack.push(Character.getNumericValue(input));
}
else if(input=='+' || input=='-' || input=='*' || input=='%' || input=='/') { // 연산자라면
int firstPop = stack.pop();
int secondPop = stack.pop();
switch (input){
case '+' :
stack.push(secondPop + firstPop);
break;
case '-' :
stack.push(secondPop - firstPop);
break;
case '*' :
stack.push(secondPop * firstPop);
break;
case '%' :
stack.push(secondPop % firstPop);
break;
case '/' :
stack.push(secondPop / firstPop);
break;
}
}else{ // 숫자 입력도 아니고 연산자 입력도 아님
System.out.println("잘못된 입력입니다.");
break;
}
}
return stack.pop();
}후기
스택을 사용한 예제들을 풀어보며 스택의 개념을 다시 한 번 더 단단하게 잡을 수 있었다. 뿐만 아니라 배열과 단순연결리스트의 장단점이 각각을 통해 구현된 스택에서도 그대로 드러남을 느꼈다. 자료구조는 직접 그려가면서 이해하고 문제를 풀어보는 것이 빨리 익힐 수 있는 지름길인 것 같다! 그리고 역시 난 자바가 제일 재밌다..🤤
