[코테공부] Stack, Queue (1)

올바른 괄호

올바른 괄호 괄호가 입력되면 올바른 괄호이면 “YES", 올바르지 않으면 ”NO"를 출력

(())() 이것은 괄호의 쌍이 올바르게 위치하는 거지만, (()()))은 올바른 괄호가 아니다.

- 입력설명 : 첫 번째 줄에 괄호 문자열이 입력됩니다. 문자열의 최대 길이는 30이다.

- 출력설명 : 첫 번째 줄에 YES, NO를 출력한다.

- 입력예제 : (()(()))(()

- 출력예제 : NO

import java.util.*;
class Main {	
	public String solution(String str){
		String answer="YES";
		Stack<Character> stack=new Stack<>();
		for(char x : str.toCharArray()){
			if(x=='(') stack.push(x);
			else{
				if(stack.isEmpty()) return "NO";
				stack.pop();
			}
		}
		if(!stack.isEmpty()) return "NO";
		return answer;
	}

	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		String str=kb.next();
		System.out.println(T.solution(str));
	}
}

 

 

 

 

 

괄호문자제거

입력된 문자열에서 소괄호 ( ) 사이에 존재하는 모든 문자를 제거하고 남은 문자만 출력하는 프로그램을 작성하라

- 입력설명 : 첫 줄에 문자열이 주어진다. 문자열의 길이는 100을 넘지 않는다.

- 출력설명 : 남은 문자만 출력한다.

- 입력예제 : (A(BC)D)EF(G(H)(IJ)K)LM(N) 

- 출력예제 : EFLM

import java.util.*;
class Main {	
	public String solution(String str){
		String answer="";
		Stack<Character> stack=new Stack<>();
		for(char x : str.toCharArray()){
			if(x==')'){
				while(stack.pop()!='(');
			}
			else stack.push(x);
		}
		for(int i=0; i<stack.size(); i++) answer+=stack.get(i);
		return answer;
	}

	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		String str=kb.next();
		System.out.println(T.solution(str));
	}
}

 

 

 

 

 

후위식 연산(postfix)

(* 후위식 연산 설명 : https://siyoon210.tistory.com/2 )

후위연산식이 주어지면 연산한 결과를 출력하는 프로그램을 작성하라

만약 3*(5+2)-9 을 후위연산식으로 표현하면 352+*9- 로 표현되며 그 결과는 12다

- 입력설명 첫 줄에 후위연산식이 주어집니다. 연산식의 길이는 50을 넘지 않습니다. 식은 1~9의 숫자와 +, -, *, / 연산자로만 이루어진다.

- 출력설명 : 연산한 결과를 출력합니다.

- 입력예제 : 352+*9-

- 출력예제 : 12

import java.util.*;
class Main {	
	public int solution(String str){
		int answer=0;
		Stack<Integer> stack = new Stack<>();
		for(char x : str.toCharArray()){
			if(Character.isDigit(x)){
				stack.push(x-48);
			}
			else{
				int rt=stack.pop();
				int lt=stack.pop();
				if(x=='+') stack.push(lt+rt);
				else if(x=='-') stack.push(lt-rt);
				else if(x=='*') stack.push(lt*rt);
				else if(x=='/') stack.push(lt/rt);
			}
		}
		answer=stack.get(0);
		return answer;
	}
	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		String str=kb.next();
		System.out.println(T.solution(str));
	}
}

# 입력값을 읽다가 숫자가 나오면 stack에 push -> 연산자가 나오면 stack.pop()을 통해 2개를 빼서 계산->

계산한 결과 값을 stack에 push -> 같은 방법으로 입력값이 없을 때 까지 반복

# 헷갈리는데 이해하면 재미있고 잘 풀릴듯? 예제 하나 잘 익혀두면 좋을거 같다

# 다른 유형의 후위식 연산 문제도 연습해봐야 될 듯