[알고리즘] Stack 이해하기 직접만들기+ Stack<E>사용하기

스택을 이용하여 괄호를 포함하는 계산식 처리 프로그램을 작성한다
단, 숫자는 자연수만 입력하여 연산은 덧셈과 뺄셈만 처리한다.

후위 표기법 수식 변환 알고리즘
1. 피연산자는 그대로 출력한다
2. 연산자는 '(' 전까지 Pop 하여 출력 후, 스택에 push 한다
3.'('는 스택에 Push
4.')' 는 '(' 전까지 pop 하여 추력 후 '('을 pop 하여 함께 제거한다.

후위 표기법 수식계산
피연산자는 push 하고 연산자는 피연산자 두 개를 pop 하여 계산 후 push 한다

 

중위 표기법: 113+11-(32-(9-2+6))

후위 표기법: 113 11 + 32 9 2 - 6 + - -

import java.util.ArrayList;
import java.util.Scanner;
import java.util.StringTokenizer;

public class StackEx {
	
	public static void main(String[] args) {
		ArrayList <String> arr=new ArrayList<String>();
		StringStack myStack=new StringStack(50);//문자열 용 스택
		IntStack intStack=new IntStack(50);// 숫자용 스택
		String cal;
		Scanner sc=new Scanner(System.in);	
		System.out.println("계산식 : ");
		cal=sc.nextLine();
		StringTokenizer st=new StringTokenizer(cal,"+-()",true);// 구분자 + - ( )
		String operator=null;
		while(st.hasMoreTokens()) {
			String check=st.nextToken().trim();// 만약 내가 연산식에 공백을 넣었더라면 공백 제거
			if(check.equals("+")||check.equals("-")) { //만약 짜른 문자열이 + - 이면
				if(myStack.isEmpty()||myStack.peek().equals("(")) {// String스택영역이 비었으면 연산자 스택에 넣거나 스택영역의 top을 확인했을때 (이면 다음 연산자 스택에 넣고
					myStack.push(check);
				}else if(myStack.peek().equals("+")||myStack.peek().equals("-")){ // 스택영역의 top을 확인했을때 +/- 연산자가 있으면 
					operator=myStack.pop(); //스택영역  pop한걸 operator변수에 넣기					
					arr.add(operator); //arraylist에 pop한 연산자 집어넣기
					myStack.push(check);// 현재 추출한 문자열을 스택에 넣기
				}				
			}else if(check.equals("(")) { //추출한 문자열이 (이면
				myStack.push(check); // 스택에 추가
			}else if(check.equals(")")) {//추출한 문자열이 ) 이면
				for(;;) {
					String repop=myStack.pop(); //pop한걸 repop변수에 넣고
					if(repop.equals("(")) { //만약 ( 를 만나면 for문 탈출
						break;
					}else {
						arr.add(repop); // (를 만나기 전까지는 pop한 값을 어레이리스트에 넣기
					}
				}
			}else {
				if(check.equals("")) {//공백처리를 위해 만들음
					continue;
				}else {
					arr.add(check);// 여기오는 것들은 다 숫자(문자열) 숫자를 어레이리스트에 추가
				}				
			}			
		}
		if(!myStack.isEmpty()) {// 만약에 남았는게 있으면
			operator=myStack.pop();// 남아있는거 pop
			arr.add(operator);//pop한거 리스트에 추가
			
		}
		System.out.println(arr.toString()); //어레이 리스트 내용 출력
		int result=0;
		for(int i=0;i<arr.size();i++) { //리스트 사이즈만큼 반복
			if(arr.get(i).equals("+")) { //리스트에있는 값이 +이면
				int first=intStack.pop(); //숫자용 스택영역에서 pop
				int second=intStack.pop();//숫자용 스택영역에서 pop
				result=first+second;// 더하기
				intStack.push(result);//값을 다시 숫자용 스택영역에 넣기
			}else if(arr.get(i).equals("-")) {// 리스트에있는 값이 -이면
				int first=intStack.pop();// 숫자용 스택영역에서 pop
				int second=intStack.pop();// 숫자용 스택영역에서 pop
				result=second-first;// 빼기
				intStack.push(result);//값 다시 숫자용 스택영역에 넣기
			}else {
				intStack.push(Integer.parseInt(arr.get(i)));//문자열(숫자)를 integer로 형변환후 숫자용 스택영역에 넣기
			}	
		}
		System.out.println(result);// 값출력
	}

}

public class StringStack{ //String 형용 스택영역클래스
		private String[] stk;
		private int capacity;
		private int ptr;
		
		public class EmptyStringStackException extends RuntimeException{ //비어있을시 예외처리용 클래스
			public EmptyStringStackException(){}
		}
		public class OverflowStringStackException extends RuntimeException{// 오버플로우용 예외처리용 클래스
			public OverflowStringStackException() {}
		}
		public StringStack(int size) { //생성자 크기를 받아옴
			ptr=0;
			capacity=size;
			try {
				stk=new String[capacity];
			}catch(OutOfMemoryError e) {
				capacity=0;			
			}		
		}
		public String push(String x) throws OverflowStringStackException{//push용
			if(ptr>=capacity) {//스택용량보다 인덱스값이 높아지면 오버플로우 예외처리
				throw new OverflowStringStackException();
			}
			return stk[ptr++]=x;// x값 스택영역에 넣기
		}
		public String pop() throws EmptyStringStackException{//pop용
			if(ptr<=0) {//인덱스값이 0보다 작아지면 그 비어있는 예외처리
				throw new EmptyStringStackException();
			}
			return stk[--ptr];//pop 시키고 인덱스값 줄이고
		}
		public String peek() throws EmptyStringStackException{// 스택의 top값을 확인하기위해
			if(ptr<=0) {
				throw new EmptyStringStackException();
			}
			return stk[ptr-1];
		}
		public boolean isEmpty() {//스택이 비어있는지 확인하기 위해
			return ptr<=0;
		}
	}

public class IntStack{// int형 용 스택 영역 클래스
		private int[] stk;
		private int capacity;
		private int ptr;
		
		public class EmptyIntStackException extends RuntimeException{
			public EmptyIntStackException(){}
		}
		public class OverflowIntStackException extends RuntimeException{
			public OverflowIntStackException() {}
		}
		public IntStack(int size) {
			ptr=0;
			capacity=size;
			try {
				stk=new int[capacity];
			}catch(OutOfMemoryError e) {
				capacity=0;			
			}		
		}
		public int push(int x) throws OverflowIntStackException{
			if(ptr>=capacity) {
				throw new OverflowIntStackException();
			}
			return stk[ptr++]=x;
		}
		public int pop() throws EmptyIntStackException{
			if(ptr<=0) {
				throw new EmptyIntStackException();
			}
			return stk[--ptr];
		}
		public int peek() throws EmptyIntStackException{
			if(ptr<=0) {
				throw new EmptyIntStackException();
			}
			return stk[ptr-1];
		}
		public boolean isEmpty() {
			return ptr<=0;
		}
	}

실행 결과

내가 Int형용 String형용 스택 클래스를 만들었는데 자바는 Stack <E>라는 좋은 api 클래스가 있습니다. 그걸 사용하면 굳이 내가 클래스를 만들지 않고 아래의 코드처럼 사용할 수 있습니다.

import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;

public class StackGEx {
	
	public static void main(String[] args) {
		Stack<Integer> intStack=new Stack<Integer>();
		Stack<String> myStack=new Stack<String>();
		ArrayList <String> arr=new ArrayList<String>();
		String cal;
		Scanner sc=new Scanner(System.in);	
		System.out.println("계산식 : ");
		cal=sc.nextLine();
		StringTokenizer st=new StringTokenizer(cal,"+-()",true);
		String operator=null;
		while(st.hasMoreTokens()) {
			String check=st.nextToken().trim();
			if(check.equals("+")||check.equals("-")) {
				if(myStack.isEmpty()||myStack.peek().equals("(")) {
					myStack.push(check);
				}else if(myStack.peek().equals("+")||myStack.peek().equals("-")){
					operator=myStack.pop();				
					arr.add(operator);
					myStack.push(check);
				}				
			}else if(check.equals("(")) {
				myStack.push(check);
			}else if(check.equals(")")) {
				for(;;) {
					String repop=myStack.pop();
					if(repop.equals("(")) {
						break;
					}else {
						arr.add(repop);
					}
				}
			}else {
				if(check.equals("")) {
					continue;
				}else {
					arr.add(check);
				}
			}			
		}
		if(!myStack.isEmpty()) {
			operator=myStack.pop();
			arr.add(operator);
			
		}
		System.out.println(arr.toString());
		int result=0;
		for(int i=0;i<arr.size();i++) {
			if(arr.get(i).equals("+")) {
				int first=intStack.pop();
				int second=intStack.pop();
				result=first+second;
				intStack.push(result);
			}else if(arr.get(i).equals("-")) {
				int first=intStack.pop();
				int second=intStack.pop();
				result=second-first;
				intStack.push(result);
			}else {
				intStack.push(Integer.parseInt(arr.get(i)));
			}	
		}
		System.out.println(result);
	}
}