$$config title: [토이프로젝트] 문자열 계산기 (스택이용) keywords: - IT - 자바 $$ [티스토리](https://smhope.tistory.com/204) # 문자열 계산기 (문제) 1. 계산식을 문자열로 받는다. (괄호 포함) 2. 만약 괄호가 있다면 그것을 먼저 처리해야한다. => 우선처리 부여 3. 공백을 허용한다.(공백을 넣지 않아도 되지만 입력할 때 두개이상의 공백은 허용하지 않음) # 1. 문자열 정리 및 배열에 저장 경우의 수 1. 숫자와 연산자 사이에 공백을 포함한다. ex) ( 50 + 50 ) 2. 숫자와 연산자 사이에 공백을 포함하지 않는다. ex) (50+50) 3. 숫자와 연산자 사이에 공백을 포함하거나 포함하지 않는다. ex) (50+ 50 ) - replace 함수를 통해 각 토큰별로 하나의 공백을 받도록 한다. - 받은 문자열은 s라고 칭한다. ```java s = s.replace("(", " ( "); s = s.replace(")", " ) "); s = s.replace("+", " + "); s = s.replace("-", " - "); s = s.replace("/", " / "); s = s.replace("*", " * "); s = s.replace(" ", " "); String[] str = s.split(" "); ``` - 세 가지 어떠한 경우라도 토큰 사이에 공백이 생긴다. ex) ( 50 + 50 ) # 2. Stack 과 값을 임시 저장하기 위한 ArrayList 선언 ```java ArrayList sb = new ArrayList<>(); Stack stack = new Stack<>(); ``` # 3. 괄호, 연산자 우선순위 부여 ```java public int priority(String operator){ if(operator.equals("(") || operator.equals(")")){ return 0; } else if (operator.equals("+") || operator.equals("-")) { return 1; } else if (operator.equals("*") || operator.equals("/")) { return 2; } return -1; } ``` # 4. 후순위 표기법으로 변환 ```java public String[] organize(String s) { boolean isBracket = false; if(s.charAt(0)=='(') { isBracket=true; } s = s.replace("(", " ( "); s = s.replace(")", " ) "); s = s.replace("+", " + "); s = s.replace("-", " - "); s = s.replace("/", " / "); s = s.replace("*", " * "); s = s.replace(" ", " "); String[] str = s.split(" "); ArrayList sb = new ArrayList<>(); Stack stack = new Stack<>(); for (int i = 0; i < str.length; i++) { String now = str[i]; switch (now){ case "+": case "-": case "*": case "/": while (!stack.isEmpty() && priority(stack.peek()) >= priority(now)) { sb.add(stack.pop()); } stack.push(now); break; case "(": stack.push(now); break; case ")": while(!stack.isEmpty() && !stack.peek().equals("(")){ sb.add(stack.pop()); } stack.pop(); break; default: sb.add(now); } } while (!stack.isEmpty()) { sb.add(stack.pop()); } if(isBracket) { sb.remove(0);} String[] result = new String[sb.size()]; for(int i = 0; i < sb.size(); i++) { result[i]=sb.get(i); } return result; } ``` - 중위 표기법을 나타낸 배열의 값(str)을 순차적으로 now에 저장한다. - switch문을 이용해 받은 값이 연산자 인지 괄호인지 숫자인지 판별 # 4-1. 에러 처리 => 쓰레기값 처리 - 문자열의 처음 값이 여는 괄호 "(" 일때 처음 값이 쓰레기값이 들어가는 현상 발생 - 문자열의 처음 값이 여는 괄호일경우 isBracket을 true로 반환 - isBracket이 true일 경우 첫번째 값 삭제 => sb를 str 배열 에 다시 저장한 이유 - 후위식 계산을 할때 str을 사용하기 더 편하기 때문 (계선 가능함) # 4-2. 숫자인 경우 ```java default: sb.add(now); ``` - 바로 sb 배열에 저장한다. # 4-3. 연산자인 경우 ```java case "+": case "-": case "*": case "/": while (!stack.isEmpty() && priority(stack.peek()) >= priority(now)) { sb.add(stack.pop()); } stack.push(now); break; ``` - 스택이 비어있지 않고, 스택의 맨 위에 연산자(stack.peek())의 우선순위 priority(stack.peek())가 현재 switch에 들어온 연산자보다 우선순위가 높을 경우. - [스택에는 연산자와 괄호만 들어간다!!] - while 조건문에 해당하는 경우 stack에서 값을 꺼내 sb에 저장한다. - 더이상 기존에 저장되어있던 stack값의 우선순위가 now보다 크지 않거나 스택이 비게되면 현재 값을 스택에 넣는다. # 4-4. "(" 여는 괄호 일 경우 ```java case "(": stack.push(now); break; ``` - 스택에 집어 넣는다. # 4-5. ")" 닫는 괄호 일 경우 ```java case ")": while(!stack.isEmpty() && !stack.peek().equals("(")){ sb.add(stack.pop()); } stack.pop(); break; ``` - 스택이 비어있지 않고, 스택에 맨 위에 연산자(stack.peek())가 닫는괄호("(")가 아니라면 스택에서 꺼내서 sb배열에 저장한다. - while이 false가 될때 까지 반복 후 "("의 값을 버리고 case ")" 종료 # 4-6. 구현 ![원본이미지](https://blog.kakaocdn.net/dn/Dze1a/btrEt1tg4cW/T8JG0p7f1wXyjj0JAq4AD0/img.gif) # 5. 후위식 계산 ```java public void resultPrint(String[] str) { Stack stack = new Stack<>(); for (String x : str) { if (!x.equals("+")&&!x.equals("-")&&!x.equals("*")&&!x.equals("/")) { stack.push(Integer.parseInt(x)); }else { int a = stack.pop(); int b = stack.pop(); switch (x) { case "+": stack.push(b+a); break; case "-": stack.push(b-a); break; case "*": stack.push(b*a); break; case "/": stack.push(b/a); break; } } } System.out.println(stack.pop()); } ``` - 스택을 이용해 단계별로 계산할 것이다. # 5-1. stack 선언 ```java Stack stack = new Stack<>(); ``` # 5-2. for each 사용 ```java for (String x : str) ``` - [자바 신속 문법](https://smhope.tistory.com/192) for each문 쓰임새 확인 # 5-3. x값이 연산자가 아닐 경우 ```java if (!x.equals("+")&&!x.equals("-")&&!x.equals("*")&&!x.equals("/")) { stack.push(Integer.parseInt(x)); } ``` - x값이 연산자가 아니다 == 숫자이다 - 숫자는 바로 스택에 저장한다. # 5-4. x값이 연산자일 경우 ```java else { int a = stack.pop(); int b = stack.pop(); switch (x) { case "+": stack.push(b+a); break; case "-": stack.push(b-a); break; case "*": stack.push(b*a); break; case "/": stack.push(b/a); break; } } } System.out.println(stack.pop()); } ``` - 스택에 저장된 값을 정수형으로 변환 - x값에 맞게 연산 진행 - 연산을 실행하고 값을 스택에 다시 저장해야한다. (아직 계산이 끝나지 않았기 때문에) # 5-5. 로직 구현 ![원본이미지](https://blog.kakaocdn.net/dn/ci68yR/btrEvJrbj6R/QKop2HHkuKODSLCxWVfgy1/img.gif) # 6. 최종 결과물 ```java //exam.Main.java package exam; import java.util.Scanner; public class Main { public static void main(String[] args) { Calc calc = new Calc(); Scanner sc = new Scanner(System.in); calc.run(sc.nextLine()); sc.close(); } } ``` ```java //exam.Calc.java package exam; import java.util.*; public class Calc { public void run(String s) { resultPrint(organize(s)); } // ================== 중위식 문자열을 후위식 표현으로 바꿔줌 ================== public String[] organize(String s) { boolean isBracket = false; if(s.charAt(0)=='(') { isBracket=true; } s = s.replace("(", " ( "); s = s.replace(")", " ) "); s = s.replace("+", " + "); s = s.replace("-", " - "); s = s.replace("/", " / "); s = s.replace("*", " * "); s = s.replace(" ", " "); String[] str = s.split(" "); ArrayList sb = new ArrayList<>(); Stack stack = new Stack<>(); for (int i = 0; i < str.length; i++) { String now = str[i]; switch (now){ case "+": case "-": case "*": case "/": while (!stack.isEmpty() && priority(stack.peek()) >= priority(now)) { sb.add(stack.pop()); } stack.push(now); break; case "(": stack.push(now); break; case ")": while(!stack.isEmpty() && !stack.peek().equals("(")){ sb.add(stack.pop()); } stack.pop(); break; default: sb.add(now); } } while (!stack.isEmpty()) { sb.add(stack.pop()); } if(isBracket) { sb.remove(0);} String[] result = new String[sb.size()]; for(int i = 0; i < sb.size(); i++) { result[i]=sb.get(i); } return result; } // ========================== 우선순위 부여 ========================== public int priority(String operator){ if(operator.equals("(") || operator.equals(")")){ return 0; } else if (operator.equals("+") || operator.equals("-")) { return 1; } else if (operator.equals("*") || operator.equals("/")) { return 2; } return -1; } // =========================== 후위식 계산 =========================== public void resultPrint(String[] str) { Stack stack = new Stack<>(); for (String x : str) { if (!x.equals("+")&&!x.equals("-")&&!x.equals("*")&&!x.equals("/")) { stack.push(Integer.parseInt(x)); }else { int a = stack.pop(); int b = stack.pop(); switch (x) { case "+": stack.push(b+a); break; case "-": stack.push(b-a); break; case "*": stack.push(b*a); break; case "/": stack.push(b/a); break; } } } System.out.println(stack.pop()); } } ``` $$youtube zsCke7ckYvo $$ # 6-1 최종결과물 에러 나누기는 소수점 구현 불가 => 개선 하면 업데이트