※ 역순 문자열 만들기
스택에 한 문자 단위로 잘라서 push했다가 pop을하면 문자열을 역으로 만들 수 있다.
※ 시스템 스택
프로그램 간의 호출과 복귀에 따른 수행 순서를 보면, 호출한 순서와 복귀하는 순서는 반대가 되어 가장 나중에 호출된 함수가 가정 먼저 실행을 완료하고 복귀한다.
따라서 함수의 호출과 복귀 순서는 스택의 LIFO 구조를 응용하여 관리하는데, 이때 사용하는 스택을 시스템 스택(System Stack)이라 한다.
함수나 서브프로그램이 호출되면 호출한 함수 수행에 필요한 지역변수, 매개변수 및 수행 후 복귀할 주소 등의 정보를 스택 프래임에 저장하여 시스템 스택에 삽입(push)한다.
시스템 스택의 top은 현재 실행중인 함수의 스택 프레임이 된다.
그리고 함수가 종료되면 top의 스택 프레임을 삭제(pop)한다. 이과정을 반복하여 전체 프로그램의 수행이 종료되면 스택은 공백 스택이 된다.
(아래 소스는 앞에서 만든 스택중 임의로 선택해서 구현함)
※ 수식의 괄호 검사
Main
public class Main {
public static void main(String[] args) {
LinkedStack st = new LinkedStack();
String parenVal = "[2-3{1+3*(2-1)}*2]";
boolean testResult = true;
for(int i=0; i < parenVal.length(); i++){
if(parenVal.charAt(i) == '[' || parenVal.charAt(i) == '{'
|| parenVal.charAt(i) == '('){
st.push(parenVal.charAt(i));
}else if(parenVal.charAt(i) == ']' || parenVal.charAt(i) == '}'
|| parenVal.charAt(i) == ')'){
char testVal = st.pop();
if(testVal =='['){
if(parenVal.charAt(i) != ']'){
System.out.println("error : 괄호 짝이 맞지 않습니다.");
testResult = false;
break;
}
}else if(testVal =='{'){
if(parenVal.charAt(i) != '}'){
System.out.println("error : 괄호 짝이 맞지 않습니다.");
testResult = false;
break;
}
}else if(testVal =='('){
if(parenVal.charAt(i) != ')'){
System.out.println("error : 괄호 짝이 맞지 않습니다.");
testResult = false;
break;
}
}
}
}
if(testResult){
System.out.println("괄호짝이 맞습니다!");
}
}
}
※ 수식의 전위, 후위 표기법 변환
- 전위 표기법 : 연산자를 앞에 표기하고 다음에 피연산자를 표기하는 법 +AB
- 중위 표기법 : 연산자를 피연산자의 가운데에 표기하는 방법 A+B
- 후위 표기법 : 연산자를 피연산자 뒤에 표기하는 방법 AB+
중위 표기법에서 전위나 후위표기법으로 바꾸려면 ( 이 괄호가 나오면 무시를 하고 수는 출력을 한다.
그리고 기호가 나오면 기호를 스택에 push하고 ) 이 괄호가 나오면 기호를 pop한다.
전위냐 후위냐에 따라 이 기호들을 적당한 위치에 넣어준다.
Main
public class Main {
public static void main(String[] args) {
String exp = "(3*5)-(6/2)";
ArrayStack as = new ArrayStack(exp.length());
String result="";
for(int i = 0; i<exp.length(); i++){
if(exp.charAt(i) =='*' || exp.charAt(i) =='/'
|| exp.charAt(i) =='+' || exp.charAt(i) =='-'){
as.push(exp.charAt(i));
}else if(exp.charAt(i) ==')'){
result = result + as.pop();
}else if(exp.charAt(i) == '1' || exp.charAt(i) == '2'|| exp.charAt(i) == '3' ||
exp.charAt(i) == '4'|| exp.charAt(i) == '5'|| exp.charAt(i) == '6'||
exp.charAt(i) == '7' || exp.charAt(i) == '8' || exp.charAt(i) == '9'){
result = result + exp.charAt(i);
}
}
result = result + as.pop();
System.out.println(result);
}
}
※ 후위 표기 수식의 연산
수가 나오면 순서대로 스택에 push를 하고 기호가 나오면 그 기호에 맞는 연산을 스택에서 가장 최근 두개의 값을 pop하여 그 기호에 맞게 계산한다.
그리고 그 결과값을 다시 스택에 push한다. 이러한 작업을 반복하면 후위 표기 수식의 연산이 된다.
public class Main {
public static void main(String[] args) {
LinkedStack ls = new LinkedStack();
String exp = "35*62/-";
int result;
for(int i =0; i< exp.length(); i++){
if(exp.charAt(i)=='1'|| exp.charAt(i)=='2'|| exp.charAt(i)=='3'||
exp.charAt(i)=='4'|| exp.charAt(i)=='5'|| exp.charAt(i)=='6'||
exp.charAt(i)=='7'|| exp.charAt(i)=='8'|| exp.charAt(i)=='9'){
ls.push(String.valueOf(exp.charAt(i)));
}else if(exp.charAt(i)=='+' || exp.charAt(i)=='-' ||
exp.charAt(i)=='*'|| exp.charAt(i)=='/'){
int num1 = Integer.parseInt(ls.pop());
int num2 = Integer.parseInt(ls.pop());
if(exp.charAt(i)=='+'){
result = num2 + num1;
ls.push(String.valueOf(result));
}else if(exp.charAt(i)=='-'){
result = num2 - num1;
ls.push(String.valueOf(result));
}else if(exp.charAt(i)=='*'){
result = num2 * num1;
ls.push(String.valueOf(result));
}else{
result = num2 / num1;
ls.push(String.valueOf(result));
}
}
}
System.out.println(ls.pop());
}
}
'플밍 is 뭔들 > 자료구조' 카테고리의 다른 글
| 04-2 큐의 구현(순차 자료구조를 이용한 큐) (0) | 2016.11.25 |
|---|---|
| 04-1 큐(Queue) (0) | 2016.11.25 |
| 03-3 스택의 구현(연결 자료구조 방식) (0) | 2016.11.25 |
| 03-2 스택의 구현(순차 자료구조) (0) | 2016.11.25 |
| 03-1 스택 (0) | 2016.11.25 |
