[문제] 백준 1918번 후위표기식

www.acmicpc.net/problem/1918

1918번: 후위 표기식

중위 -> 후위 표기식 변경 방법

 

1. 피연산자 -> 출력

 

2. * / 는 스택에 push

   단, 스택이 비어있지 않고 top에 * / 가 있다면 pop하고 스택에 push 한다.

 

3. + - 는 스택에 push

   단. 스택이 비어있지 않은 경우, 빌 때 까지 pop한 후에 스택에 넣는다.

   스택에 ( 가 있다면, ( 가 나올 때 까지만 pop한다. 그 후, 스택에 넣는다.

 

4. ( 가 나오면 스택에 push

 

5.  ) 가 나오면 ( 만날 때까지 pop한다.

 

6. 모든 과정이 끝나면 -> 스택 비어있을 때까지 pop

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String s = in.readLine();
		int len = s.length();
		String postS = postfix(s, len);
		System.out.println(postS);
	}

	static String postfix(String s, int len) {
		StringBuilder sb = new StringBuilder();
		Stack<Character> stack = new Stack<>();

		for (int i = 0; i < len; i++) {
			char c = s.charAt(i);

			if (c == '*' || c == '/') {
				if (!stack.isEmpty()) {
					if (stack.peek() == '*' || stack.peek() == '/') {
						sb.append(stack.pop());
					}
				}
				stack.push(c);
			} else if (c == '+' || c == '-') {
				if(stack.isEmpty()) {
					stack.push(c);
				}else {
					while(!stack.isEmpty()) {
						if(stack.peek()=='(') break;
						sb.append(stack.pop());
					}
					stack.push(c);
				}
			}
			else if(c == '(') {
				stack.push(c);
			}
			else if(c == ')') {
				while(stack.peek() != '(') {
					sb.append(stack.pop());
				}
				stack.pop();
			}else {
				sb.append(c);
			}
		}
		while(!stack.isEmpty()) {
			sb.append(stack.pop());
		}
		return sb.toString();
	}

}