[Java] 스택을 이용한 후위표기 계산기

중위표기를 후위표기로 바꾸는 계산기 실습

1. stack을 직접 구현

2. 컬렉션 stack 사용

---

1. stack 직접 구현

input : 113 + 11 - (32 - (9 - 2 + 6))

output : 113 11 + 32 9 2 - 6 + - -

 

1. strToStrArr() 메서드를 통해 문자열을 분리한다.

2. 분리한 문자열을 if문을 통해 후위계산식을 구한다.

3. 구한 후위계산식을 calC()메서드를 통해 계산결과를 얻는다.

 

//후위표기법 (스택 구현)
class MyStack {
	private String[] stk; //연산자 담을 배열
	private int capacity; //스택 용량
	private int ptr; // 스택 포인터
	
	public MyStack() {
		ptr = -1; //-1을 포인터로 설정하면 현재 위치를 가르킨다. 0=다음위치
		capacity = 20;
		stk = new String[capacity];
	}
	
	//stk이 비어있지 않으면 마지막 값을 리턴
	public String getTop() {
		return (this.isEmpty()) ? null : stk[ptr];
	}
	
	//pop
	public String pop(){
		if(this.isEmpty()) {
			System.out.println("can't pop");
			return null;
		} else {
			String temp = stk[ptr--];
	        return temp;	
		}
	}
	
	//push
	public void push(String s) {
		if(ptr<capacity) {
			stk[++ptr] = s;
		} else {
			System.out.println("can't push");
		}
	}
	
	//출력
	public void disp() {
		System.out.print("[");
		for(String s : stk) {
			if(s!=null) {
				System.out.print(s+" ");				
			}
		}
		System.out.print("]\n");
	}
	
	//스택이 비어있는지 확인
	public boolean isEmpty() {
		return (stk[0] == null) ? true : false;
	}
	
	//식을 한 줄로 입력하면 스트링어레이로 바꿔주는 메서드
	public String[] strToStrArr(String str) {
		System.out.println(str);
		str = str.replace("(", "( ");
		str = str.replace(")", " )");
		String[] arr = str.split(" ");
		return arr;
	}
	
	// 최종결과 계산 (후위계산 식 입력)
	public int calC(String resultStr) {
		String[] cal_result = resultStr.split(" ");
		int result = 0;

		for(String s : cal_result) {
			switch (s) {
			case "+":
				result = Integer.valueOf(this.pop()) + Integer.valueOf(this.pop());
				this.push(String.valueOf(result));
				break;
				
			case "-":
				result = -Integer.valueOf(this.pop()) + Integer.valueOf(this.pop());
				this.push(String.valueOf(result)); 
				break;

			default:
				this.push(s);
				break;
			}
		}
		return result;
	}
}

public class PostfixNotation {
	public static void main(String[] args) {
		MyStack ms = new MyStack();
		
		String a = "113 + 11 - (32 - (9 - 2 + 6))";
		String[] arr = ms.strToStrArr(a); //메서드를 통해 식을 한 단어씩 분리
		String result = ""; //최종 결과를 담을 변수
	
		for (String s : arr) {
			ms.disp(); //현재 스택 상태를 표시
			
			switch (s) {
			case "+":
				if(ms.isEmpty()) { //스택이 비어있으면 그냥 push
					ms.push(s);
				} else if(ms.getTop().equals("(")){ // "("가 나오면 그냥 push
					ms.push(s);
				} else {
					result += ms.pop()+" "; //아니면 pop -> push
					System.out.println(result);
					ms.push(s);
				}
				break;
				
			case "-":
				if(ms.isEmpty()) {
					ms.push(s);
				} else if(ms.getTop().equals("(")){
					ms.push(s);
				} else {
					result += ms.pop()+" ";
					System.out.println(result);
					ms.push(s);
				}
				break;

			// ( 는 그냥 push
			case "(": 
				ms.push(s);
				break;
			
			// ( 가 나올때 까지 pop, 안나오면 출력 
			case ")":
				while(true) {
					if(ms.getTop().equals("(")) {
						ms.pop();
						break;
					} else {
						result += ms.pop()+" ";
						System.out.println(result);
					}
				}
				break;
			
			// 피연산자는 그냥 출력
			default:
				result += s+" ";
				System.out.println(result);
				break;
			}
		}
		
		// 스택이 비어있지 않으면 pop 1회 수행
		if(!ms.isEmpty()) {
			result += ms.pop();
		}
		
		System.out.println("------최종------");
		System.out.println("후위 표기법 : "+result);
		
		//결과계산
		MyStack cal = new MyStack();
		int cal_result = cal.calC(result);
		System.out.println("결과 : "+cal_result);
	}		
}

---

2. 컬렉션 스택

import java.util.Stack;

//후위표기법 (컬렉션 스택 사용)
public class PostfixNotation2 {
	public static void main(String[] args) {
		Stack<String> ms = new Stack<>();

		String a = "113 + 11 - (32 - (9 - 2 + 6))";
		String[] arr = strToStrArr(a); // 메서드를 통해 식을 한 단어씩 분리
		String result = ""; // 최종 결과를 담을 변수

		for (String s : arr) {
			switch (s) {
			case "+":
				if (ms.isEmpty()) { // 스택이 비어있으면 그냥 push
					ms.push(s);
				} else if (ms.peek().equals("(")) { // "("가 나오면 그냥 push
					ms.push(s);
				} else {
					result += ms.pop() + " "; // 아니면 pop -> push
					System.out.println(result);
					ms.push(s);
				}
				break;

			case "-":
				if (ms.isEmpty()) {
					ms.push(s);
				} else if (ms.peek().equals("(")) {
					ms.push(s);
				} else {
					result += ms.pop() + " ";
					System.out.println(result);
					ms.push(s);
				}
				break;

			// ( 는 그냥 push
			case "(":
				ms.push(s);
				break;

			// ( 가 나올때 까지 pop, 안나오면 출력
			case ")":
				while (true) {
					if (ms.peek().equals("(")) {
						ms.pop();
						break;
					} else {
						result += ms.pop() + " ";
						System.out.println(result);
					}
				}
				break;

			// 피연산자는 그냥 출력
			default:
				result += s + " ";
				System.out.println(result);
				break;
			}
		}

		// 스택이 비어있지 않으면 pop 1회 수행
		if (!ms.isEmpty()) {
			result += ms.pop();
		}

		System.out.println("------최종------");
		System.out.println("후위 표기법 : " + result);

		// 결과계산
		MyStack cal = new MyStack();
		int cal_result = cal.calC(result);
		System.out.println("결과 : " + cal_result);
	}

	// 식을 한 줄로 입력하면 스트링어레이로 바꿔주는 메서드
	public static String[] strToStrArr(String str) {
		System.out.println(str);
		str = str.replace("(", "( ");
		str = str.replace(")", " )");
		String[] arr = str.split(" ");
		return arr;
	}

	// 최종결과 계산 (후위계산 식 입력)
	public int calC(String resultStr) {
		Stack<String> ms = new Stack<>();
		String[] cal_result = resultStr.split(" ");
		int result = 0;

		for (String s : cal_result) {
			switch (s) {
			case "+":
				result = Integer.valueOf(ms.pop()) + Integer.valueOf(ms.pop());
				ms.push(String.valueOf(result));
				break;

			case "-":
				result = -Integer.valueOf(ms.pop()) + Integer.valueOf(ms.pop());
				ms.push(String.valueOf(result));
				break;

			default:
				ms.push(s);
				break;
			}
		}
		return result;
	}
}

 

 

---

느낀점

스택을 직접 구현하니 포인터를 컨트롤하기가 힘들었다.

결국 에러가 많이 나서 효율적으로 메서드를 사용하지 못해 아쉬웠다.

컬렉션 stack은 정말 편리했다.

직접 구현하는 것을 더 연습하자 !

---

참고 문헌 : Do it! 자바 완전정복