문제
수식이 주어졌을 때, +, -, * 의 우선순위를 재정의하고 그 우선순위를 통해 계산했을 때 결과값의 절대값이 가장 큰 값을 구하는 문제이다.
(단, +, - > * 와 같이 두 부호의 우선순위가 같을 수는 없다.)
입력
100-200*300-500+20
출력
60420
접근
우선, 이 문제를 보고 식을 후위 연산식으로 바꾼 후 스택 계산기를 이용해 계산하는 방법이 떠올랐다. 그 전에, 수식에서 연산자만 뽑아내고 그들에게 우선순위만 부여해줬다.
연산자 우선순위 설정
int[][] priorities = {{1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}};
char[] operators = {'\u0000', '\u0000', '\u0000'};초기 우선순위 및 연산자 배열이다. 연산자가 +, -, * 이며 최대 6가지의 경우의 수가 나올 수 있기에 2차원 배열로 한 번에 정의했다.
public void setPriority(String exp) {
boolean isPlusExist = false; // 더하기 설정 여부
boolean isMinusExist = false; // 빼기 설정 여부
boolean isMultiplyExist = false; // 곱하기 설정 여부
for (int i = 0; i < exp.length(); i++) {
char c = exp.charAt(i);
if (c == '+' && !isPlusExist) {
isPlusExist = true;
operators[operatorCnt++] = '+';
} else if (c == '-' && !isMinusExist) {
isMinusExist = true;
operators[operatorCnt++] = '-';
} else if (c == '*' && !isMultiplyExist) {
isMultiplyExist = true;
operators[operatorCnt++] = '*';
}
}
}+, -. *에 대해 중복 없이 배열에 저장해주었다.
후위 연산식 구하기
public String getPostfix(int turn, String exp){
String res = "";
Stack<Character> stack = new Stack();
for (int i = 0; i < exp.length(); i++){
char c = exp.charAt(i);
if (c == '(') {
res += " ";
stack.push(c);
} else if (c == ')') {
res += " ";
while (stack.peek() != '(') {
res += stack.pop();
}
stack.pop();
} else if (c == '+' || c == '-' || c == '*') {
while (!stack.isEmpty()) {
int p1 = getPriority(turn, c);
int p2 = getPriority(turn, stack.peek());
// 숫자가 작을수록 우선순위 높음
if (p1 >= p2) {
res += stack.pop();
} else {
break;
}
}
res += " ";
stack.push(c);
} else {
res += c;
}
}
while (!stack.isEmpty()) {
res+= stack.pop();
}
return res;
}-
'(' 인 경우
스택에 집어넣는다. -
')' 인 경우
스택에 '(' 가 발견될 때까지 스택에 있는 부호들을 하나씩 꺼내면서 후위 계산식 문자열에 붙인다.
(잘못된 계산식이 아닌 이상 스택에 '(' 은 반드시 남아있다.)
전부 꺼내고 난 후 스택에 남아있는 '(' 도 꺼낸 후 갖다 버린다. -
'+', '-', '*' 인 경우
스택에 남아있는 연산자와 본인의 연산자 우선순위를 비교한 후
스택에 남아있는 연산자 우선순위가 본인의 연산자 우선순위보다 높을 경우 스택에서 연산자를 꺼내어 후위 연산자 문자열에 붙인다.
(위의 코드같은 경우 부등호를 반대로 하여 = 연산자도 같이 붙게 되었다.) -
그 외 정수인 경우
후위 계산식 문자열에 갖다 붙인다.
계산
public String getPostfix(int turn, String exp){
String res = "";
Stack<Character> stack = new Stack();
for (int i = 0; i < exp.length(); i++){
char c = exp.charAt(i);
if (c == '(') {
res += " ";
stack.push(c);
} else if (c == ')') {
res += " ";
while (stack.peek() != '(') {
res += stack.pop();
}
stack.pop();
} else if (c == '+' || c == '-' || c == '*') {
while (!stack.isEmpty()) {
int p1 = getPriority(turn, c);
int p2 = getPriority(turn, stack.peek());
// 숫자가 작을수록 우선순위 높음
if (p1 >= p2) {
res += stack.pop();
} else {
break;
}
}
res += " ";
stack.push(c);
} else {
res += c;
}
}
while (!stack.isEmpty()) {
res+= stack.pop();
}
return res;
}위에서는 연산자에 대한 스택이 필요했다면, 이제는 정수에 대한 스택이 필요하다. 후위 계산식에서 정수가 나오면 스택에 넣는 방식이다.
(단, 현재 후위 연산식은 문자열이기 때문에 숫자로 변환하여 넣는 작업이 좀 필요하다.)
'+', '-', '*' 연산자가 나오면 스택에 있는 두 정수를 꺼내어 계산한 후 다시 스택에 넣어준다. 단, 여기서 주의할 점이 한 가지 있다.
| 3 <- top |
| 5 |
| 1 |
| 10 |
이 상태에서 두 정수를 꺼내면 위에서부터 꺼내게 될 것이고
3 -> 5 순서대로 나올 것이다. 각각을 n1, n2라고 가정하면,
n1 = 3
n2 = 5
인 상태고 '-' 연산을 해야 하는 상황이라면
n2 - n1 = 5 - 3 = 2
와 같이 계산해야 한다!
즉, 두 수에 대한 연산을 할 때, 스택에서 나중에 나온 정수가 연산자 왼쪽에, 스택에서 먼저 나온 정수가 연산자 오른쪽에 위치하게 된다.
코드
import java.util.*;
class Solution {
int operatorCnt = 0;
int[][] priorities = {{1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}};
char[] operators = {'\u0000', '\u0000', '\u0000'};
public int getPriority (int turn, char operator) {
int p = 0;
for (int i = 0; i < operatorCnt; i++) {
if (operators[i] == operator) {
p = i;
break;
}
}
return priorities[turn][p];
}
public void setPriority(String exp) {
boolean isPlusExist = false; // 더하기 설정 여부
boolean isMinusExist = false; // 빼기 설정 여부
boolean isMultiplyExist = false; // 곱하기 설정 여부
for (int i = 0; i < exp.length(); i++) {
char c = exp.charAt(i);
if (c == '+' && !isPlusExist) {
isPlusExist = true;
operators[operatorCnt++] = '+';
} else if (c == '-' && !isMinusExist) {
isMinusExist = true;
operators[operatorCnt++] = '-';
} else if (c == '*' && !isMultiplyExist) {
isMultiplyExist = true;
operators[operatorCnt++] = '*';
}
}
}
public String getPostfix(int turn, String exp){
String res = "";
Stack<Character> stack = new Stack();
for (int i = 0; i < exp.length(); i++){
char c = exp.charAt(i);
if (c == '(') {
res += " ";
stack.push(c);
} else if (c == ')') {
res += " ";
while (stack.peek() != '(') {
res += stack.pop();
}
stack.pop();
} else if (c == '+' || c == '-' || c == '*') {
while (!stack.isEmpty()) {
int p1 = getPriority(turn, c);
int p2 = getPriority(turn, stack.peek());
// 숫자가 작을수록 우선순위 높음
if (p1 >= p2) {
res += stack.pop();
} else {
break;
}
}
res += " ";
stack.push(c);
} else {
res += c;
}
}
while (!stack.isEmpty()) {
res+= stack.pop();
}
return res;
}
public long getAnswer(String exp){
Stack<Long> stack = new Stack();
long result = 0;
for (int i = 0; i < exp.length(); i++) {
char c = exp.charAt(i);
long value = 0;
if ('0' <= c && c <= '9') {
while (i < exp.length() && '0' <= c && c <= '9') {
value = value * 10 + (c - '0');
i++;
c = exp.charAt(i);
}
i--;
stack.push(value);
} else if (c != ' ') {
long n1 = stack.pop();
long n2 = stack.pop();
long res = 0;
if (c == '+') {
res = n2 + n1;
} else if (c == '-') {
res = n2 - n1;
} else if (c == '*') {
res = n2 * n1;
}
stack.push(res);
}
}
result = stack.pop();
return Math.abs(result);
}
public long solution(String expression) {
setPriority(expression);
String postfix;
long tempAnswer = 0;
long answer = 0;
for (int i = 0; i < 6; i++) {
postfix = getPostfix(i, expression); // 후위 계산식
tempAnswer = getAnswer(postfix); // 답 계산
if (answer < tempAnswer) {
answer = tempAnswer;
}
}
return answer;
}
}오랜만에 스택 계산기를 다시 구현해봤는데, 조금씩 헷갈려하는 부분을 다시 잡는 시간이 되었다고 생각한다.
