연결리스트를 이용한 다항식을 계산하고 사용자가 입력한 문자열을 파싱하는 Polynominal 코드 만들기

 

자료구조 수업에서 연결리스트를 이용한 다항식 계산 프로그램을 작성하라는 과제를 받았다.

 

https://youtu.be/UviSUv21iB8

 

여기 유튜브에서 하는것과 비슷하게 만들면 될듯하다

 

기능

1. f = 5x 같은 문자열을 입력하면 f라는 Poly 클래스를 만들고 5x Term 클래스를 만들어 Poly에 연결한다.

2. f = 6x + 7x^2 같은 문자열을 한번 더입력하면 f 자리에 6x + 7x^2을 넣는다.

3. print f를 입력하면 f 함수를 출력한다.

4. calc f 2를 입력하면 f함수에 따른 2를 계산한 결과를 출력한다.

5. f = f + g를 입력하면 함수 f와 g를 계산한 함수를 저장한다.

 

연결리스트를 이용하여 메모리가 가능한 한도내에 무제한으로 저장할 수 있도록 만든다.

자바 객체 변수는 객체의 주소를 저장하기 때문에 연결리스트를 만들 수 있고

c언어 보다 지원하는 함수와 기능이 많기 때문에 만들기 쉽다.

 

 

Main.java

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    static ArrayList<Polynominal> polynominals = new ArrayList<>();    // 여러개의 다항식을 저장할 리스트 생성

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);   // 입력받을 스캐너

        while(true){
            System.out.print("$ ");
            String input = scanner.nextLine();  // 다항식 입력 받음
            input = removeSpace(input); // 공백 제거한 스트링을 받음
            if(input.equals("exit")) break;
            else if(input.length() >= 4 && input.startsWith("calc")){
                printCal(input);
            } else if(input.length() >= 5 && input.startsWith("print")) {
                printPoly(input);
            } else if(input.length() >= 5 && input.charAt(0) >= 'a' && input.charAt(0) <= 'z'
                    && input.charAt(2) >= 'a' && input.charAt(2) <= 'z'
                    && input.charAt(4) >= 'a' && input.charAt(4) <= 'z'){
                addPoly(input);
            }
            else {
                Polynominal poly = new Polynominal();
                int recent = -1;
                int index = -1;
                for(Polynominal p : polynominals){
                    index++;
                    if(p.getName() == input.charAt(0)){
                        recent = index;
                        break;
                    }
                }
                poly.setName(input.charAt(0));  // poly의 이름 설정
                ArrayList<Character> strToArray = strToArray(input);    // 조각낸 String을 배열로 받음
                poly = initPoly(poly, strToArray);

                if(recent == -1) {
                    polynominals.add(poly);
                } else {
                    polynominals.set(recent, poly);
                }
            }
        }
    }

    public static void printPoly(String str){
        for(Polynominal p : polynominals){
            if(p.getName() == str.charAt(5)){
                p.printTerm();
            }
        }
        System.out.println();
    }

    public static void addPoly(String str){
        // 사용자가 입력한 것이 식을 더하는 것인지 체크
        char a, b, c;
        a = str.charAt(0);
        b = str.charAt(2);
        c = str.charAt(4);

        int i1 = 0, i2 = 0, i3 = 0;


        for(int i = 0; i< polynominals.size(); i++){
            if (polynominals.get(i).getName() == a) {
                i1 = i;
            }
            if (polynominals.get(i).getName() == b) {
                i2 = i;
            }
            if (polynominals.get(i).getName() == c) {
                i3 = i;
            }
        }

        Polynominal p2 = polynominals.get(i2), p3 = polynominals.get(i3);

        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append(p2.termToString());
        stringBuilder.append(p3.termToString());

        String tmptmp = stringBuilder.toString();

        Polynominal p1 = new Polynominal();
        p1.setName(a);
        StringBuilder stringBuilder1 = new StringBuilder();
        stringBuilder1.append(p1.getName());
        stringBuilder1.append('=');
        stringBuilder1.append(tmptmp);

        String input = stringBuilder1.toString();
        input = removeSpace(input); // 공백 제거한 스트링을 받음
        ArrayList<Character> strToArray = strToArray(input);    // 조각낸 String을 배열로 받음
        initPoly(p1, strToArray);

        polynominals.set(i1, p1);

    }

    public static void printCal(String str){
        // 사용자가 입력한 것이 식을 더하는 것인지 체크
        for(Polynominal p : polynominals){
            if(p.getName() == str.charAt(4)){
                // 입력한 다항식의 이름과 같은걸 찾았을 경우
                StringBuilder stringBuilder = new StringBuilder();
                for(int i=5; i<str.length(); i++){
                    stringBuilder.append(str.charAt(i));
                }
                p.printCal(Integer.parseInt(stringBuilder.toString()));
                // 계산한 것을 출력완료
            }
        }
    }

    public static Polynominal initPoly(Polynominal p, ArrayList<Character> arrayList){
        for(int i=0; i<arrayList.size(); i++){
            // for문을 돌리면서 배열을 하나씩 체크하는데 +, -, 배열 끝에 만났을 때
            // 현재 인덱스보다 하나 작은 인덱스를 만들고 그걸 기준으로 하나씩 줄여가며
            // 이전의 + - 를 만날 때 까지 while 문을 돌림
            if((arrayList.get(i) == '+' || arrayList.get(i) == '-' || i == arrayList.size() - 1) && i != 0){
                int tmpIndex = i-1;
                boolean exFlag = false;
                int ttt = 0;
                while(true){
                    if(arrayList.get(tmpIndex) == '+' || arrayList.get(tmpIndex) == '-') break;
                    tmpIndex--;
                }

                // 지금 tmpIndex는 이전의 +,-를 만난상태
                // tmpIndex를 복사한 tmpIndex2를 증가시키면서 x를 만나거나 +, -를 만날때까지 while문을 돌리며 증가시킴
                // 왜냐 x나 + -를 만난다는 것은 tmpIndex부터 tmpIndex2까지의 숫자는 coef가 될것이기 때문이다
                int tmpIndex2 = tmpIndex + 1;
                while(true){
                    if(arrayList.get((tmpIndex2)) == 'x' && tmpIndex2 != arrayList.size() - 1) {
                        ttt = 1;
                        break;
                    } else if (arrayList.get((tmpIndex2)) == 'x' && tmpIndex2 == arrayList.size() - 1){
                        ttt = 0;
                        break;
                    }
                    else if(arrayList.get((tmpIndex2)) == '+' || arrayList.get((tmpIndex2)) == '-'){
                        ttt = 1;
                        exFlag = true;
                        break;
                    }
                    else if(tmpIndex2 == arrayList.size() - 1) {
                        // 차수가 없음
                        tmpIndex2++;
                        ttt = 0;
                        exFlag = true;
                        break;
                    }
                    tmpIndex2++;
                }

                // tmpIndex부터 tmpIndex2까지의 문자를 coef에 넣었음
                Term t = new Term();
                StringBuilder stringBuilder = new StringBuilder();
                for(int u=tmpIndex; u<tmpIndex2; u++){
                    stringBuilder.append(arrayList.get(u));
                }
                String tmpStr = stringBuilder.toString();
                t.setCoef(Integer.parseInt(tmpStr));

                // 여기까지는 coef 까지 추출 완료

                // x가 1차항인지 다차항인지 상수 하나인지 체크
                if(exFlag) {
                    // 상수 하나 차수가 없음
                    t.setExpo(0);
                } else {
                    // x는 무조건 있음
                    if(arrayList.get(tmpIndex2+ttt) == '^'){
                        // 1차항 이상
                        // tmpIndex2에 ^ 다음 인덱스 번호를 넣음
                        // tmpIndex에 tmpIndex2를 넣고 tmpIndex2를 +, -를 만날 때 까지 증가시킴
                        tmpIndex2 = tmpIndex2+2;
                        tmpIndex = tmpIndex2;

                        while(true){
                            if(arrayList.get(tmpIndex2) == '+' || arrayList.get(tmpIndex2) == '-') {
                                break;
                            } else if (tmpIndex2 == arrayList.size() - 1){
                                tmpIndex2++;
                                break;
                            }
                            tmpIndex2++;
                        }
                        // tmpIndex2는 지금 + -를 만나기 직전 인덱스
                        stringBuilder = new StringBuilder();
                        for(int u=tmpIndex; u < tmpIndex2; u++){
                            stringBuilder.append(arrayList.get(u));
                        }
                        int tmpExpo = Integer.parseInt(stringBuilder.toString());
                        t.setExpo(tmpExpo);

                    } else {
                        // 무조건 1차항
                        t.setExpo(1);
                    }
                }
                // expo 까지 완료
                
                // term이 완성되었으니 poly에 넣음
                /*System.out.println("===============");
                System.out.println(t.getCoef() + " " + t.getExpo());
                System.out.println("===============");*/

                p.addTerm(t);
            }
        }
        return p;
    }

    // 공백 제거
    public static String removeSpace(String str){
        StringBuilder stringBuilder = new StringBuilder();
        for(int i=0; i<str.length(); i++){
            if(str.charAt(i) != ' '){
                stringBuilder.append(str.charAt(i));
            }
        }
        str = stringBuilder.toString();
        return str;
    }
    
    // = 이후의 모든 문자열을 하나 하나 조각내서 배열에 넣음
    public static ArrayList<Character> strToArray(String str){
        ArrayList<Character> arrayList = new ArrayList<>();
        int eqIndex = str.indexOf('=');
        if (eqIndex != -1){
            if(str.charAt(eqIndex+1) != '+' && str.charAt(eqIndex+1) != '-'){
                arrayList.add('+'); // +, -가 없을 경우 양수로 판단하고 +를 붙여줌
            }
            for(int i=eqIndex+1; i<str.length(); i++){
                arrayList.add(str.charAt(i));
            }
        } else {
            System.out.println("식이 잘못 되었습니다");
            System.exit(1);
        }
        return arrayList;
    }
}

 

Polynominal.java

import java.util.ArrayList;

public class Polynominal {
    private char name;
    private Term term = null;
    private int size = 0;

    public char getName() {
        return name;
    }

    public void setName(char name) {
        this.name = name;
    }

    public Term getTerm() {
        return term;
    }

    public void setTerm(Term term) {
        this.term = term;
    }

    public int getSize() {
        return size;
    }

    public void setSize(int size) {
        this.size = size;
    }

    public void addTerm(Term t){
        if(this.term == null){
            // 현재 term이 null일경우 아무것도 없기 때문에 동적으로 생성
            Term term1 = new Term();
            term1.setCoef(t.getCoef());
            term1.setExpo(t.getExpo());
            this.term = term1;
            this.size++;
        } else {
            // 아닐경우 주소를 넣음
            Term term1 = this.term;
            while(true){
                // term을 받아왔는데 같은 차수가 있을 수 있으니 더해줘야함
                if(t.getExpo() == term1.getExpo()){
                    // 지금은 같으니까 원래있던 값에 더하면 되겠지
                    term1.setCoef(term1.getCoef() + t.getCoef());
                    break;
                } else {
                    // 없으면 term의 next가 널인지 체크 널이면 생성
                    if(term1.getNext() == null){
                        Term term2 = new Term();
                        term2.setCoef(t.getCoef());
                        term2.setExpo(t.getExpo());
                        term1.setNext(term2);
                        this.size++;
                        // term2를 새로 만들어서 추가하려는 term t를 넣고
                        // term의 next에 term2를 넣음
                        break;
                    }  else {
                        // 원하는걸찾지못했음 다음으로 넘어감
                        term1 = term1.getNext();
                    }
                }
            }

        }
    }

    public void printTerm(){
        if(this.term == null)
            System.out.print("다항식이 올바르지 않습니다.");
        else{
            System.out.print("$ " + this.name + "(x) =");
            // 출력
            // 일단 first term을 넣음
            int tecentExpo;

            Term term = this.term;
            // size를 이용해서 반복문 출력
            for(int i=0; i<this.size; i++){
                if(i != 0){
                    if(term.getCoef() < 0){
                        System.out.print(" - ");
                    } else {
                        System.out.print(" + ");
                    }
                } else System.out.print(" ");
                if(term.getExpo() == 1){
                    System.out.print(Math.abs(term.getCoef()) + "x");
                } else if(term.getExpo() == 0){
                    System.out.print(Math.abs(term.getCoef()));
                } else {
                    System.out.print(Math.abs(term.getCoef()) + "x^" + term.getExpo());
                }
                term = term.getNext();
            }
        }
    }

    public String termToString(){
        StringBuilder stringBuilder = new StringBuilder();
        Term term = this.term;
        // size를 이용해서 반복문 출력
        for(int i=0; i<this.size; i++){
            if(term.getCoef() < 0){
                stringBuilder.append('-');
            } else {
                stringBuilder.append('+');
            }
            stringBuilder.append(Math.abs(term.getCoef()) + "x^" + term.getExpo());
            term = term.getNext();
        }
        return stringBuilder.toString();
    }

    public void printCal(int n){
        if(this.term != null){
            Term term1 = this.term;
            int cal = 0;
            for(int i = 0; i<this.size; i++){
                cal += term1.cal(n);
                term1 = term1.getNext();
            }
            System.out.println("$ " + cal);
        }
    }
}

 

Term.java

public class Term {
    private int coef;
    private int expo;
    private Term next = null;

    public int getCoef() {
        return coef;
    }

    public void setCoef(int coef) {
        this.coef = coef;
    }

    public int getExpo() {
        return expo;
    }

    public void setExpo(int expo) {
        this.expo = expo;
    }

    public Term getNext() {
        return next;
    }

    public void setNext(Term next) {
        this.next = next;
    }

    public int cal(int n){
        int tmp = this.coef * (int)Math.pow(n, this.expo);
        return tmp;
    }
}