sm 기술 블로그

[자바] 문자열 계산기 (스택이용) 본문

토이프로젝트

[자바] 문자열 계산기 (스택이용)

sm_hope 2022. 6. 10. 21:07

문자열 계산기

(문제)

  1. 계산식을 문자열로 받는다. (괄호 포함)
  2. 만약 괄호가 있다면 그것을 먼저 처리해야한다. => 우선처리 부여
  3. 공백을 허용한다.(공백을 넣지 않아도 되지만 입력할 때 두개이상의 공백은 허용하지 않음)

1. 문자열 정리 및 배열에 저장

경우의 수

  1. 숫자와 연산자 사이에 공백을 포함한다. ex) ( 50 + 50 )
  2. 숫자와 연산자 사이에 공백을 포함하지 않는다. ex) (50+50)
  3. 숫자와 연산자 사이에 공백을 포함하거나 포함하지 않는다. ex) (50+ 50 )
  • replace 함수를 통해 각 토큰별로 하나의 공백을 받도록 한다.
  • 받은 문자열은 s라고 칭한다.
	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 선언

 	ArrayList<String> sb = new ArrayList<>();
        Stack<String> stack = new Stack<>();

3. 괄호, 연산자 우선순위 부여

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. 후순위 표기법으로 변환

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<String> sb = new ArrayList<>();
        Stack<String> 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. 에러 처리

=> sb를 str 배열 에 다시 저장한 이유

  • 후위식 계산을 할때 str을 사용하기 더 편하기 때문 (개선 가능함)

=> 쓰레기값 처리

  • 문자열의 처음 값이 여는 괄호 "(" 일때 처음 값이 쓰레기값이 들어가는 현상 발생
  • 문자열의 처음 값이 여는 괄호일경우 isBracket을 true로 반환
  • isBracket이 true일 경우 첫번째 값 삭제

4-2. 숫자인 경우

		default:
                   sb.add(now);
  • 바로 sb 배열에 저장한다.

4-3. 연산자인 경우

		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. "(" 여는 괄호 일 경우

		case "(":
                    stack.push(now);
                    break;
  • 스택에 집어 넣는다.

4-5. ")" 닫는 괄호 일 경우

		case ")":
                    while(!stack.isEmpty() && !stack.peek().equals("(")){                    	                              	
                    		sb.add(stack.pop());                  	
                    }
                    stack.pop();
                    break;
  • 스택이 비어있지 않고, 스택에 맨 위에 연산자(stack.peek())가 닫는괄호("(")가 아니라면 스택에서 꺼내서 sb배열에 저장한다.
  • while이 false가 될때 까지 반복 후 "("의 값을 버리고 case ")" 종료

4-6. 로직 구현

5. 후위식 계산

 public void resultPrint(String[] str) {
    	
    	Stack<Integer> 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 선언

	Stack<Integer> stack = new Stack<>();

5-2. for each 사용

	for (String x : str)

5-3. x값이 연산자가 아닐 경우

	if (!x.equals("+")&&!x.equals("-")&&!x.equals("*")&&!x.equals("/")) { 
	    	  stack.push(Integer.parseInt(x));
	      }
  • x값이 연산자가 아니다 == 숫자이다
  • 숫자는 바로 스택에 저장한다.

5-4. 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());
	 }
  • 스택에 저장된 값을 정수형으로 변환
  • x값에 맞게 연산 진행
  • 연산을 실행하고 값을 스택에 다시 저장해야한다. (아직 계산이 끝나지 않았기 때문에)

5-5. 로직 구현

6. 최종 결과물

//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();

	}

}

//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<String> sb = new ArrayList<>();
        Stack<String> 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<Integer> 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());
	 }

    	
    
}

https://youtu.be/zsCke7ckYvo

6-1 최종결과물 에러

나누기는 소수점 구현 불가 => 개선 하면 업데이트

 

 

'토이프로젝트' 카테고리의 다른 글

Ajax로 좋아요 버튼 기능 구현(with Thymeleaf)  (0) 2022.08.20
[리액트 React] 명언게시판  (0) 2022.05.28
리액트 계산기  (0) 2022.05.19
'토이프로젝트' Related Articles more
Comments