-
백준 1935번 후위표기식2 :: 마이구미알고리즘 풀이/스택, 큐 2017. 7. 16. 21:36반응형
이번 글은 백준 알고리즘 문제 1935번 "후위표기식2" 를 다뤄본다.
1918번 "후위표기식" 문제는 중위표기식에서 후위표기식으로 변환하는 문제였다. - 관련 링크
이번 문제는 후위표기식을 계산하는 문제로써, 1918번 문제를 푼 후, 풀어보면 좋은 문제가 된다.
중위표기식에서 후위표기식 변환 문제도 사실상 방법만 알면 간단했다.
후위표기식의 계산 또한, 단순하다.
- 피연산자는 스택에 push 한다.
- 연산자가 나오면 스택에 있는 수를 2번 pop 한다.
- pop한 두 수를 연산자에 맞게 계산한 후, 다시 push 한다.
- 모든 계산이 끝나면, 스택의 top이 최종 계산 값이 된다.
for (int i = 0; i < len; i++) { char ch = s[i]; switch(ch) { case '+': case '-': case '*': case '/': cal(stack, stack.pop(), stack.pop(), ch); break; default: stack.push(array[ch - 'A']); break; } }
위 흐름대로 코드를 구현하면, 끝이다.
컴퓨터 또한, 이렇게 단순하게 계산하기 때문에, 후위표기식을 사용한다.
실제 스택의 이용 사례를 보여주고 있는 문제이기 때문에, 좋은 문제라 생각한다.
본인은 스택에 있어서, 1918번과 1935번 후위표기식에 관한 문제를 푸는 것을 지향한다.
Github - https://github.com/hotehrud/acmicpc/blob/master/algorithm/stack/1935.java
12345678910111213141516171819202122232425262728293031323334353637383940414243444546private void solve() {// http://mygumi.tistory.com/184int n = sc.nextInt();char[] s = sc.next().toCharArray();int len = s.length;double[] array = new double[n];Stack<Double> stack = new Stack<Double>();for (int i = 0; i < n; i++) {array[i] = sc.nextInt();}for (int i = 0; i < len; i++) {char ch = s[i];switch(ch) {case '+':case '-':case '*':case '/':cal(stack, stack.pop(), stack.pop(), ch);break;default:stack.push(array[ch - 'A']);break;}}System.out.format("%.2f", stack.peek());}public static void cal(Stack<Double> stack, double a, double b, char op) {switch(op) {case '+':stack.push(b + a);break;case '-':stack.push(b - a);break;case '*':stack.push(b * a);break;case '/':stack.push(b / a);break;}}cs 반응형'알고리즘 풀이 > 스택, 큐' 카테고리의 다른 글
백준 14891번 톱니바퀴 :: 마이구미 (3) 2018.04.01 백준 7662번 이중 우선순위 큐 :: 마이구미 (0) 2017.09.22 백준 2014번 소수의 곱 :: 마이구미 (2) 2017.07.16 백준 1918번 후위표기식 :: 마이구미 (2) 2017.07.09 백준 2841번 외계인의 기타 연주 :: 마이구미 (0) 2017.07.06