[LeetCode Top Interview 150]
[문제 링크]
[문제 설명]
역 폴란드 표기법(=후위 표기법) tokens의 표현식을 나타내는 문자열 배열이 주어진다. 이 표현의 값을 구하여라(계산). 표현식의 값을 나타내는 integer를 반환한다.
참고사항
- 유효한 연산자는 '+', '-', '*'및 입니다 '/'.
- 각 피연산자는 정수이거나 다른 표현식일 수 있습니다.
- 두 정수 사이의 나눗셈은 항상 0을 향해 잘립니다 .
- 0으로 나누는 일은 없을 것입니다.
- 입력은 역방향 폴란드어 표기법으로 유효한 산술 표현식을 나타냅니다.
- 답과 모든 중간 계산은 32비트 정수로 표현될 수 있습니다.
Example 1:
Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9
Example 2:
Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6
Example 3:
Input: tokens = ["10","6","9","3","+","-11","","/","","17","+","5","+"]
Output: 22
Explanation: ((10 (6 / ((9 + 3) -11))) + 17) + 5
= ((10 (6 / (12 -11))) + 17) + 5
= ((10 (6 / -132)) + 17) + 5
= ((10 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
[처음에 내가 생각해 본 방법]
처음에는 문자열 배열 tokens의 값들이 모두 stack에 담겨야 한다고 생각하고, 배열 3개를 만들어서 for문으로 tokens의 값들을 반복문을 돌리면서 그 안에 반복문과 조건문을 통해서.. 이런 식으로 접근을 했었는데 문제를 풀다보니까 꼭 그럴 필요가 없겠다는 생각이 들었다. 조건에 사칙연산이 꼭 stack에 들어가야 한다는 조건이 없었고, 출력 결과로 연산의 결과를 도출하면 되는 것이니까 말이다. 처음에 작성한 코드는 그래서 복잡하고, 실행했을 때 컴파일 오류가 뜨거나, 통과되지 못했다.
[시행 착오 코드1]
class Solution {
public int evalRPN(String[] tokens) {
ArrayList<String> a = new ArrayList();
ArrayList<String> b = new ArrayList();
ArrayList<String> c = new ArrayList();
String operA = "";
String operC = "";
int result = 0;
for(int i = 0; i < tokens.length; i++){
if(tokens[i].contains("+") || tokens[i].contains("-")
|| tokens[i].contains("*") || tokens[i].contains("/")){
// tokens 값 중 사칙연산을 배열에 추가
if(b.isEmpty()){
b.add(tokens[i]);
System.out.println("b" + b);
}else {
;
}
}
if(c.isEmpty()){
c.add(tokens[i]);
System.out.println("c" + c);
}else if(a.isEmpty()){
a.add(tokens[i]);
System.out.println("a" + a);
}else{
;
}
if(b.size() == 1 || c.size() == 1 || a.size() == 1){
int A = 0;
int C = 0;
if(b.size() == 1){
if(b.get(0).contains("+")){
C = Integer.parseInt(c.get(0));
A = Integer.parseInt(a.get(0));
result = C+A;
b.remove(b.size()-1);
c.remove(operC);
a.remove(operA);
}else if(b.get(0).contains("-")){
C = Integer.parseInt(c.get(0));
A = Integer.parseInt(a.get(0));
result = C-A;
b.remove(b.size()-1);
c.remove(operC);
a.remove(operA);
}else if(b.get(0).contains("*")){
C = Integer.parseInt(c.get(0));
A = Integer.parseInt(a.get(0));
result = C*A;
b.remove(b.size()-1);
c.remove(operC);
a.remove(operA);
}else if(b.get(0).contains("/")){
C = Integer.parseInt(c.get(0));
A = Integer.parseInt(a.get(0));
result = C/A;
b.remove(b.size()-1);
c.remove(operC);
a.remove(operA);
}else{
c.remove(operC);
a.remove(operA);
}
}
}
}
return result;
}
}[그렇다면 어떻게? 처음부터 접근을 다시 해보자]
내가 문제를 잘못 이해했었구나, 인지하고 그때부터 접근 방법을 다시 고민하기 시작했다. tokens에 포함된 사칙연산에 대한 조건문이 필수적으로 있어야겠다는 생각. Stack의 속성? 특수한 성격을 활용해서 풀어야겠다는 생각.. 등이 정리되면서 어느 정도 이렇게 풀면 되겠구나 싶은 감이 잡히면서 Stack을 활용해서 다시 풀어봐야겠다고 생각했다. 그래서 접근부터 다르게 다시 작성해보았다. 몇 번의 과정을 거쳐 탄생한 제출 코드는 다음과 같다.
[최종 제출 코드]
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack();
String operator = "+-*/" ;
for(String t : tokens){
if(operator.contains(t) && !stack.isEmpty()){
int a = stack.pop();
int b = stack.pop();
int result = 0;
if(t.equals("+")){
result = b+a;
}else if(t.equals("-")){
result = b-a;
}else if(t.equals("*")){
result = b*a;
}else {
result = b/a;
}
stack.push(result);
}else{
stack.push(Integer.parseInt(t));
}
}
return stack.pop();
}
}1) Stack 선언
2) operator 연산자들을 따로 변수로 선언
3) tokens 문자열 배열을 for문을 통해 반복문 돌리면서 stack에 추가하는데
4) 만약, operator에 tokens 값이 포함이 되어있고 && stack이 비어있지 않다면, stack에서 pop() 함수를 통해 현재 stack 중에 가장 마지막에 삽입된 요소를 꺼내서 차례로 a,b 변수에 담아줌. 그리고 결과를 담을 result 변수 선언 및 초기화
5) 만약 tokens 배열의 값이 연산자 중 "+"이면, b+a 값을 result 변수에 할당 / 이런 식으로 각 연산자들에 대한 조건문을 분기해줌
여기서 b 변수를 먼저 써주는 이유 : tokens = ["2","1","+","3","*"] 값일 때
stack = [2, 1] 이 삽입되고, top에 있던 1이 a / 맨 처음 담긴 2는 b가 됨. (a=1, b=2) / 연산자는 "+"이므로, 2+1 = 3이 된다.
6) 연산자에 대한 조건문이 끝나면, result 값을 다시 stack에 push 해줌 (2+1 연산값 3을 stack에 삽입함)
7) 그럼, 이전에 tokens 배열에 이미 존재하고 있던 숫자 3과, 새롭게 stack에 삽입된 3에 대한 연산이 또 이뤄짐. 이번엔 연산자가 "x"이므로 3x3=9
8) 연산자에 대한 조건문이 끝나면, result 값을 다시 stack에 push 해줌 (3*3 연산값 9를 stack에 삽입함)
9) 반복문이 다 돌고 반환하는 return 값은 stack.pop(); => 결국 최종 마지막 값은 9이 반환된다.
10) 만약, operator에 tokens 값이 포함이 되어있지 않고 && stack이 비어있다면, String타입의 숫자를 int타입으로 변환하여 stack에 삽입해줌.
