728x90
스택 (Stack)
- 자료를 한 방향으로만 쌓는 자료구조
- LIFO (Last In First Out 후입선출 : 마지막에 들어온 것이 가장 먼저 나간다)
- push : 스택에 data를 넣는 것
- pop : 스택 맨 위의 data를 빼는 것
- peek : pop과 유사하게 맨 위의 data를 반환하지만 스택에서 제거하지는 않는다.
- top : 가장 마지막에 추가된 data의 위치 (가장 맨위)
- 가장 마지막에 push 한 data가 가장 먼저 pop 된다.
오버플로우 (Overflow)
: 자료가 스택 크기를 넘어서서 더 이상 push 하지 못할 때 발생
언더플로우 (Underflow)
: 스택에 자료가 남아있지 않아서 더 이상 pop하지 못할 때 발생
배열로 구현해보기
public class Main {
static final int STACK_SIZE = 100;
static int stack[] = new int[100];
static int top = -1;
static void push(int data)
{
stack[++top] = data;
}
static int pop()
{
return stack[top--];
}
static int peek()
{
return stack[top];
}
public static void main(String[] args) {
push(3);
push(5);
push(8);
System.out.println(pop());
System.out.println(pop());
System.out.println(peek());
System.out.println(peek());
/* 결과 :
8
5
3
3
*/
}
}
※ 참고
: 자바 Collection에 이미 List를 상속받는 Stack 라이브러리가 구현이 되어있다.
스택 응용
1. 역순 문자열 만들기
- LIFO의 원리를 이용하여 역순으로 문자열 만들기
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
String str = "ABC";
Stack stack = new Stack();
//스택에 push
for(int i=0;i<str.length();i++)
stack.push(str.charAt(i));
//역순 문자열 만들기
String str_reverse = "";
for (int i=0;i<str.length();i++)
str_reverse += stack.pop();
System.out.println(str_reverse);
}
}
2. 괄호 검사
- 입력받은 수식에서 괄호 (Bracket)이 쌍에 맞게 사용되었는지 검사
- 여는 괄호, 닫는 괄호가 쌍을 이루는가
- 여러 개의 괄호가 중첩되었을 때 가장 안쪽 괄호부터 차례대로 처리되는지 점검
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
public class Main {
static boolean isBracketMatching(char open, char close)
{
if(open == '(' && close == ')')
return true;
else if(open == '{' && close == '}')
return true;
else if(open == '[' && close == ']')
return true;
else
return false;
}
static boolean isCloseBracket(char c)
{
if(c == ')' || c == ']' || c == '}')
return true;
else
return false;
}
static boolean isOpenBracket(char c)
{
if(c == '(' || c == '[' || c == '{')
return true;
else
return false;
}
static boolean checkBracketMatching(String input)
{
Stack<Character> stack = new Stack();
for(int i=0;i<input.length();i++)
{
char c = input.charAt(i);
//여는 괄호 검사
if(isOpenBracket(c))
{
stack.push(c);
}
else if(isCloseBracket(c))
{
char open = stack.peek();
//매칭 검사
if(!isBracketMatching(open, c))
return false;
else
stack.pop();
}
}
//스택이 비어있지않다면 close bracket이 부족하다는 뜻
if(stack.isEmpty())
return true;
else
return false;
}
public static void main(String[] args) {
System.out.println(checkBracketMatching("(A+b) * [c+{d/e}+f]"));
System.out.println(checkBracketMatching("[A+b+{c+d)+e]"));
/* 결과
true
false
*/
}
}
3. 수식 계산과 표기법
- 중위 표기법 (Infix Notation)
- 일반적으로 쓰는 수식 표기법
- 연산자가 피연산자 중간에 온다.
- EX) a + b, a * b + c * d
- 후위 표기법 (Postfix Notation)
- 연산자가 피연산자 뒤에 온다.
- 중위 표기법과 달리 계산방향에 차이가 없다는 장점이 있다.
- EX) 중위 : A - (B + C) * D → 후위 : A B C + D * -
- 수식 입력 받아서 계산
- 중위 표기법 → 후위 표기법 변환
- 후위 표기법 수식 계산
- 1, 2단계 모두 스택 (Stack) 사용
중위 표기법 → 후위 표기법 변환
- 숫자 (Digit)를 만나면 Postfix 변수에 바로 저장
- 연산자 (Operator)를 만나면 Stack에 push
- 만약 peek가 연산자라면 pop한 후에 Postfix에 저장 → 그 다음 현재 연산자 push
- 열린 괄호 (Open Bracket) 만나면 Stack에 push
- 닫힌 괄호 (Close Bracket) 만나면 열린 괄호를 만날 때까지 연산자들을 pop한 후에 Postfix에 저장
- 반복문 종료 후 Stack에 남은 연산자들 모조리 pop하여 Postfix에 저장
//중위 표기법 -> 후위 표기법 변환
static String infixToPostfix(String infix)
{
Stack<Character> stack = new Stack<>();
String postfix = "";
for(int i=0;i<infix.length();i++)
{
char c = infix.charAt(i);
if(Character.isDigit(c))//CASE : 숫자
{
postfix += c;
}
else if(isOperator(c))// CASE : 연산자
{
if(!stack.isEmpty() && isOperator(stack.peek()))
postfix += stack.pop();
stack.push(c);
}
else if (isOpenBracket(c))//CASE : 열린 괄호
{
stack.push(c);
}
else if(isCloseBracket(c))//CASE : 닫힌 괄호
{
char pop_item = stack.pop();
while(!isOpenBracket(pop_item))
{
postfix += pop_item;
pop_item = stack.pop();
}
}
}
//남은 연산자 출력
while(!stack.isEmpty())
postfix += stack.pop();
return postfix;
}
후위 표기법 계산 메서드
- 숫자는 Stack에 push
- 연산자를 만나면 피연산자 2개를 pop해서 계산 후 그 결과를 다시 push
- 최종 결과 pop
//후위 표기법 수식 계산
static int postfixCalculate(String expression)
{
Stack<Integer> stack = new Stack<>();
for(int i=0;i<expression.length();i++)
{
char c = expression.charAt(i);
if(Character.isDigit(c)) //CASE : 숫자
{
stack.push(c - 48);
}
else//CASE : 연산자
{
int b = stack.pop();
int a = stack.pop();
stack.push(calculate(a,b,c));
}
}
return stack.pop();
}
전체 코드
import java.util.Stack;
public class Main {
//후위 표기법 수식 계산
static int postfixCalculate(String expression)
{
Stack<Integer> stack = new Stack<>();
for(int i=0;i<expression.length();i++)
{
char c = expression.charAt(i);
if(Character.isDigit(c)) //CASE : 숫자
{
stack.push(c - 48);
}
else//CASE : 연산자
{
int b = stack.pop();
int a = stack.pop();
stack.push(calculate(a,b,c));
}
}
return stack.pop();
}
//중위 표기법 -> 후위 표기법 변환
static String infixToPostfix(String infix)
{
Stack<Character> stack = new Stack<>();
String postfix = "";
for(int i=0;i<infix.length();i++)
{
char c = infix.charAt(i);
if(Character.isDigit(c))//CASE : 숫자
{
postfix += c;
}
else if(isOperator(c))// CASE : 연산자
{
if(!stack.isEmpty() && isOperator(stack.peek()))
postfix += stack.pop();
stack.push(c);
}
else if (isOpenBracket(c))//CASE : 열린 괄호
{
stack.push(c);
}
else if(isCloseBracket(c))//CASE : 닫힌 괄호
{
char pop_item = stack.pop();
while(!isOpenBracket(pop_item))
{
postfix += pop_item;
pop_item = stack.pop();
}
}
}
//남은 연산자 출력
while(!stack.isEmpty())
postfix += stack.pop();
return postfix;
}
static int calculate(int a, int b, char c)
{
if(c == '+')
return a + b;
else if(c == '-')
return a - b;
else if(c == '*')
return a * b;
else
return a / b;
}
static boolean isCloseBracket(char c)
{
if(c == ')' || c == ']' || c == '}')
return true;
else
return false;
}
static boolean isOpenBracket(char c)
{
if(c == '(' || c == '[' || c == '{')
return true;
else
return false;
}
static boolean isOperator(char c)
{
if(c == '+' || c == '-' || c == '*' || c == '/')
return true;
return false;
}
public static void main(String[] args) {
System.out.println(postfixCalculate(infixToPostfix("(3+1)*2")));
/* 결과
8
*/
}
}
728x90
'Computer Science > 자료구조' 카테고리의 다른 글
| [자료구조] 트리 (Tree) (0) | 2020.08.31 |
|---|---|
| [자료구조] 큐 (Queue) (0) | 2020.08.31 |
| [자료구조] Trie 트라이 (0) | 2020.08.26 |
| [자료구조] 연결 리스트의 종류 (0) | 2020.08.25 |
| [자료구조] 리스트 (List) (0) | 2020.08.25 |
댓글