어떤 단어가 들어왔을 때 그 데이터를 뒤집어서 출력할 경우 스택의 구조를 활용할 수 있다.
1. Push 메서드를 활용하여서 단어를 한 글자씩 stack자료형에 넣어준다.
2. 스택에서 Pop 메서드를 활용하여서 단어를 뒤에서부터 하나씩 빼면 뒤집힌 단어를 구할 수 있다.
import java.util.*;
public class BalancedParantneass {
public static void main(String[] args) {
Stack<Character> stk = new Stack<>(); // <int> → <Character>로 수정
String s;
Scanner sc = new Scanner(System.in);
s = sc.next();
// 문자열을 문자 하나씩 스택에 push
for (int i = 0; i < s.length(); i++) {
stk.push(s.charAt(i));
}
// 스택에서 문자를 pop하여 출력 (역순 출력)
while (!stk.isEmpty()) {
System.out.print(stk.pop());
}
sc.close();
}
}
Balanced Parenthess
괄호가 열린 괄호와 닫힌 괄호가 밸런스 있게 잘 표현되었는지 확인하는 알고리즘이다.
ex) (1+2)+((1*3)+3): 벨런스 맞춰진 괄호로 이루어져 있다.
(6+3)+(((1+2)*3: ((1+2)*3에서 닫힌 괄호 하나가 부족하기 때문에 밸런스 있는 형태라고 보기 어렵다.
import java.util.*;
public class BalancedParantneass {
public static void main(String[] args) {
Stack<Character> stk = new Stack<>();
String s;
Scanner sc = new Scanner(System.in);
s = sc.next();
boolean isBalanced = true;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(' || s.charAt(i) == '{' || s.charAt(i) == '[') {
stk.push(s.charAt(i));
} else if (s.charAt(i) == ')' || s.charAt(i) == '}' || s.charAt(i) == ']') {
if (stk.isEmpty()) {
isBalanced = false;
break;
}
char c = stk.peek();
if ((s.charAt(i) == ')' && c == '(') ||
(s.charAt(i) == '}' && c == '{') ||
(s.charAt(i) == ']' && c == '[')) {
stk.pop(); // 올바른 짝이면 pop
} else {
isBalanced = false;
break;
}
}
}
// 남아있는 괄호가 있으면 불균형
if (!stk.isEmpty()) {
isBalanced = false;
}
if (isBalanced) {
System.out.println("Balanced");
} else {
System.out.println("Not Balanced");
}
}
}
More Complex Stack Applications: Infix, Polish prefix, Polish postfix notation
중위 표기식(infix) A+B, 3*(4+5)
전위 표기식(prefix) + A B, * 3 + (4 5)
후위 표기식(postfix) A B +, 3 4 5 + *
다음은 후위 표기식 표기법과 연산을 진행하는 코드이다.
import java.util.*;
public class Post_Pre {
public static boolean isNumber(String str) { //string을 정수로 변환
try {
Double.parseDouble(str);
return true;
} catch (NumberFormatException msg) {
return false;
}
}
//오퍼래이터(연산자)의 순서를 리턴해준다.
//숫자가 클수록 우선 순위가 커지고 -1이면 연산자가 아니다.
public static int getPrecedence(String op){
if(op.equals("+")||op.equals("-")) return 1;
else if(op.equals("*")||op.equals("/")) return 2;
return -1;
}
public static List<String> infixToPostfix(String infix_notation) throws Exception {
String[] elements = infix_notation.split(" "); //띄어쓰기에 따라서 분활해준다.
Stack<String> opStk = new Stack<>(); //연산자와 괄호를 넣어준다.
List<String> output = new ArrayList<>(); //postfix의 결과를 리스트에 저장해준다.
for (String i : elements) {
if (isNumber(i)) {
output.add(i);
} else if (i.equals("(")) {
//열린 괄호일 경우에는 opStk에 그냥 넣어준다.
opStk.push(i);
} else if (i.equals(")")) {
//만약 닫힌 괄호일 경우에는 스택에 넣어둔 연산자들을 꺼내준다.
//만약 열린 괄호를 만난다면 종료한다.
while (!opStk.isEmpty() && !opStk.peek().equals("(")) {
output.add(opStk.pop());
}
if (opStk.isEmpty()) {
throw new Exception("균형 잡힌 괄호 쌍이 존재하지 않음");
}
//오퍼레이터에 있는 열린 괄호를 제거해준다.
opStk.pop();
} else if ("+-*/".contains(i)) {
//+,-,*,/ 연산자가 있으면 실행한다.
//스택에서 맨 위에 있는 연산자의 우선 순위가 크거나 같을 때 까지 반복해준다.
while (!opStk.isEmpty() &&
getPrecedence(opStk.peek()) >= getPrecedence(i)) {
output.add(opStk.pop());
}
opStk.push(i);
} else { //아니라면 예외 발생한다.
throw new Exception("알 수 없는 오퍼랜드: " + i);
}
}
//남은 연산자를 처리해준다.
while (!opStk.isEmpty()) { //열린 괄호가 있으면 예외를 발생시킨다.
if (opStk.peek().equals("(")) {
throw new Exception("괄호가 열리고 닫히지 않았습니다.");
}
//결과 리스트에 연산자를 넣어준다.
output.add(opStk.pop());
}
return output;
}
public static double calculatePostfix(List<String> postfix) throws Exception {
Stack<Double> stk = new Stack<>();
for (String i : postfix) {
if (isNumber(i)) {
stk.push(Double.parseDouble(i));
} else if ("+-*/".contains(i)) {
if (stk.size() < 2) throw new Exception("연산자 수가 피연산자보다 많습니다.");
double b = stk.pop();
double a = stk.pop();
//스위치 문을 활용하여서 연산자에 따라서 연산을 진행해준다.
switch (i) {
case "+": stk.push(a + b); break;
case "-": stk.push(a - b); break;
case "*": stk.push(a * b); break;
case "/":
if (b == 0) throw new Exception("0으로 나눌 수 없습니다.");
stk.push(a / b);
break;
}
}
}
if (stk.size() != 1) throw new Exception("수식이 올바르지 않습니다.");
return stk.pop();
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("======= MyCalculator ========");
System.out.println("MyCalculator 사용을 환영합니다.");
while (true) {
System.out.println("\nInfix로 수식을 입력하시오.");
System.out.print(">");
String infix_notation = sc.nextLine();
try {
List<String> postfix_notation = infixToPostfix(infix_notation);
System.out.print("Postfix로 변환: ");
for (String i : postfix_notation) {
System.out.print(i + " ");
}
System.out.println();
System.out.print("계산을 시작할까요? (Y/N)\n> ");
String ans = sc.nextLine();
if (ans.equals("Y")) {
double result = calculatePostfix(postfix_notation);
System.out.println("계산 값: " + result);
}
System.out.print("계속하시겠습니까? (Y/N)\n> ");
String cont = sc.nextLine();
if (!cont.equals("Y")) {
System.out.println("사용해주셔서 감사합니다.");
System.out.println("프로그램을 종료합니다.");
break;
}
} catch (Exception e) {
System.out.println("에러: " + e.getMessage());
}
}
}
}
Backtracking
보통 recursion과 stack과 같이 쓰인다.
import java.util.Stack;
public class BacktrackingExample {
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
solve(0, stack);
}
public static void solve(int step, Stack<Integer> path) {
if (step == 3) {
System.out.println("해답: " + path);
return;
}
for (int i = 1; i <= 3; i++) {
path.push(i); // 선택
solve(step + 1, path); // 다음 단계 재귀 호출
path.pop(); // 백트래킹
}
}
}
step이 3이 될 때 까지 계속 반복해 주는 solve 코드인데, path 스택에 넣고 빼면서 반복해 준다.
Runtime Stack
호출 스택이라고도 부르는 데 함수 호출 정보들 저장하는 메모리 영역을 의미한다.
즉, 해당 함수의 지역 변수, 매개 변수, 복귀 주소 등의 정보가 스택 프레임이라는 구조로 스택에 쌓인다.
함수가 종료된다면 스택 프레임은 pop 되어서 종료된다.
public class Main {
public static void main(String[] args) {
A();
}
static void A() {
B();
}
static void B() {
System.out.println("Hello");
}
}
