✅ 후위연산식이 주어지면 연산한 결과를 출력하세요
💡 후위연산식
숫자를 앞에 쓰고 연산자를 뒤에 쓰는 방식
3*(5+2)-9 을 후위연산식으로 표현하면 352+*9-
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| class Main {
public int solution(String input){
int answer=0;
Stack<Integer> stack= new Stack<>();
for(char x: input.toCharArray()){
if(Character.isDigit(x)){ //check if char is number
stack.push(x-48); //change char to int
}else{
int a= stack.pop();
int b= stack.pop();
if(x== '+'){
stack.push(b+a);
}else if(x=='-'){
stack.push(b-a);
}else if(x=='*'){
stack.push(b*a);
}else if(x=='/'){
stack.push(b/a);
}
}
}
answer= stack.get(0); //하나남은 숫자 answer에 추가
return answer;
}
public static void main(String[] args) {
Main T = new Main();
Scanner sc= new Scanner(System.in);
String input= sc.next();
System.out.print(T.solution(input));
}
}
//⭐️input:
//352+*9-
//⭐️output:
//12
|
🔵 ThingsILearned
✔️ How to check if char is number
1
| Character.isDigit(char);
|
✔️ How to change char to int
1
2
3
4
5
6
| //방법 1
int charInt= Character.getNumericValue(char);
//방법 2
//0이 ascii로 치면 48
int charInt= char - 48;
|
🟢
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| class Main {
public int solution(String input){
int answer=0;
Stack<Integer> stack= new Stack<>();
for(char x: input.toCharArray()){
if(Character.isDigit(x)){ //check if char is number
stack.push(Character.getNumericValue(x)); //char to int
}else{
int a= stack.pop();
int b= stack.pop();
if(x== '+'){
answer= b+a;
}else if(x=='-'){
answer= b-a; //⭐️
}else if(x=='*'){
answer= b*a;
}else if(x=='/'){
answer= b/a; //⭐️
}
stack.push(answer);
}
}
return answer;
}
public static void main(String[] args) {
Main T = new Main();
Scanner sc= new Scanner(System.in);
String input= sc.next();
System.out.print(T.solution(input));
}
}
|
- 숫자는 stack에 추가한다.
- 연산자를 만나면 stack 가장 위에 있는 숫자 두 개를
pop해서 연산한다.
- ⭐️ 이 때 가장 위에 있는 숫자가 두 번째 숫자가 되고, 그 다음 있는 숫자가 첫 번쨰 숫자가 되어야 한다.
- 그 결과를 또 stack에 추가한다.
🟢 중위표기식 ➡️ 후위표기식(괄호 없음)
💡 차량기지 알고리즘
연산자가 나오면 stack에 추가하는데,
지금 넣으려는 연산자가 기존에 있는 연산자보다 우선순위가 낮으면,
stack에 있는 모든 연산자들을 answer에 추가하고 stack은 pop.
그리고 지금 넣으려는 연산자는 stack에 추가.
1+2*3 ➡️ 123*+
1*2+3 ➡️ 12*3+
1+2*3+4/5 ➡️ 123*+45/+
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| class Main {
public String solution(String input){
String answer="";
Stack<Character> stack= new Stack<>();
for(char x: input.toCharArray()){
if(Character.isDigit(x)){
answer +=x;
}else{
if(stack.isEmpty()){
stack.push(x);
}else{
char peek= stack.peek();
if(x== '+' || x=='-'){
if(peek== '+' || peek=='-'){
stack.push(x);
}else if(peek=='*' || peek=='/'){
while(!stack.isEmpty()) answer +=stack.pop();
stack.push(x);
}
}else if(x=='*' || x=='/'){
if(peek== '+' || peek=='-'){
stack.push(x); //
}else if(peek=='*' || peek=='/'){
stack.push(x);
}
}
}
}
}
for(int i=stack.size()-1; i>=0; i--){
answer += stack.get(i);
}
return answer;
}
public static void main(String[] args) {
Main T = new Main();
Scanner sc= new Scanner(System.in);
String input= sc.next();
System.out.print(T.solution(input));
}
}
|
🟢 중위표기식 ➡️ 후위표기식(함수로우선순위 정해서, 괄호⭕️)
(3+5*(4-6)/2) ➡️ 3546-*2/+
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| class Main {
public int priority(char x){
switch(x){
case '*' :
case '/' :
return 2; //곱하기와 나누기 우선순위가 더 높음
case '+' :
case '-' :
return 1;
default :
return 0;
}
}
public String solution(String input){
String answer="";
Stack<Character> stack= new Stack<>();
for(char x: input.toCharArray()) {
if (Character.isDigit(x)) {
answer += x;
} else if(x == '('){
stack.push(x);
} else if(x == ')'){
while(!stack.isEmpty() && stack.peek() != '('){ //1️⃣
answer+= stack.pop();
}
stack.pop();
}else{ //연산자일 때
//stack에 넣으려고 하는 연산자의 우선순위가
//stack안에 들어있는 연산자의 우선순위보다 높으면 넣을 수 있고
//낮으면 다 빼고 새로운 연산자만 추가
while(!stack.isEmpty() && priority(stack.peek()) >=priority(x)){ //2️⃣
answer += stack.pop();
}
stack.push(x);
}
}
while(!stack.isEmpty()){
answer +=stack.pop();
}
return answer;
}
public static void main(String[] args) {
Main T = new Main();
Scanner sc= new Scanner(System.in);
String input= sc.next();
System.out.print(T.solution(input));
}
}
|
🔴 TroubleShooting
1️⃣ stack에서 ) 만나면 (만날 때까지 다 pop하새요
- stack이 비어있지 않고
stack.peek()했을 때 (이 아니면
pop해서 정답에다가 추가하고
- 마지막으로
(을 pop하기 위해서 while문 밖에서 pop을 한번 한다.
2️⃣ stack에 +가 있을 때 *는 추가할 수 있지만, *가 있는데 +는 추가할 수 없다.
그러니까 우선순위가 더 높은 연산자는 추가할 수 있지만,
우선순위가 낮은 연산자는 stack에 있는 모든 연산자를 pop한 후에 추가
- 지금 추가하려는 연산자가
priority(x)
- stack에 있는 연산자
priority(stack.peek())
- 보다 우선순위가 낮니??
- 그러면 추가 못해
- stack에 있는 모든 연산자를
pop 하고 추가하렴
🟢 중위표기식 ➡️ 후위표기식(map으로우선순위 정해서, 괄호⭕️)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| class Main {
public String solution(String input){
HashMap<Character, Integer> map= new HashMap<>();
map.put('(', 0);
map.put('+', 1);
map.put('-', 1);
map.put('*', 2); //곱하기와 나누기 우선순위가 더 높음
map.put('/', 2);
String answer="";
Stack<Character> stack= new Stack<>();
for(char x: input.toCharArray()) {
if (Character.isDigit(x)) {
answer += x;
} else if(x == '('){
stack.push(x);
} else if(x == ')'){
while(!stack.isEmpty() && stack.peek() != '('){
answer+= stack.pop();
}
stack.pop();
}else{ //연산자일 때
while(!stack.isEmpty() && map.get(stack.peek()) >= map.get(x)){
answer += stack.pop();
}
stack.push(x);
}
}
while(!stack.isEmpty()){
answer +=stack.pop();
}
return answer;
}
public static void main(String[] args) {
Main T = new Main();
Scanner sc= new Scanner(System.in);
String input= sc.next();
System.out.print(T.solution(input));
}
}
|