SWEA- 1233 계산기 2

<후위표기식> STACK이용

 

연산자마다 우선순위를 부여해주어야함.

내 연산순위> 스택의 peek연산순위 = push.

내 연산순위<= 스택의 peek 연산순위 = pop후 문자열에 붙이기 and 나를 push.

후위 표기 연산이 이해가 잘 가지않아 그림을 그려보았다.

과정이 두개 필요하다

1. 후위표기식을 만들기

2. 후위표기연산을 하기

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.Stack;

public class Solution{
	static int oson(char c) {
		if(c=='*') return 10;
		else if(c=='+') return 5;
		return -1;
	}
	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("input/swea_Cal2.txt"));
		Scanner sc = new Scanner(System.in);
		for (int tc = 1; tc <= 10; tc++) {
			int N = sc.nextInt();
			String str = sc.next();
			String cal ="";
			Stack<Character> stk = new Stack<Character>();
			for (int i = 0; i < str.length(); i++) {
				char c = str.charAt(i);
				//숫자일경우 문자열에 붙이기
				if(c-'0'>=0 && c-'0'<=9) {
					cal += String.valueOf(c);
				}
				//문자일경우(*, +일경우 스택이 비었나 확인 ->스택에 넣어야하기때문)
				else {
					if(stk.isEmpty()) {
						stk.push(c);
					}
					else {
						if(oson(stk.peek()) < oson(c)) {
							stk.push(c);
						}
						else {
							
							cal += String.valueOf(stk.pop());
							stk.push(c);
						}
					}
				}
			}
			while(!stk.isEmpty()) {
				cal += String.valueOf(stk.pop());
			}
			//후위표기식을 계산
			Stack <Integer> sk = new Stack<Integer>();
			
			for (int i = 0; i < cal.length(); i++) {
				char c = cal.charAt(i);
				//숫자이면 무조건 푸시
				if(c-'0'>=0 && c-'0'<=9) {
					sk.push(c-'0');
				}else{
				//* 이나 + 이면 2번 팝 계산후 푸시
				int num1=sk.pop();
				int num2=sk.pop();
				if(c=='*') {
					sk.push(num1*num2);
				}else if(c=='+') {
					sk.push(num1+num2);
				}
				}
				
			}
			int res = sk.pop();
			System.out.printf("#%d %d\n",tc,res);
		}
	
	
	}
}