스 택 에서 대수 덧셈 문제 해결 (자바 구현)

16676 단어 데이터 구조
* 글 의 내용 은 (2 판) 유소 정 두 가 편집장 을 선택 한 것 에서 유래 되 었 습 니 다 * 이 시 리 즈 는 학습 기록 으로 글 의 내용 이 잘못 되 었 다 면 지적 해 주 십시오. 감사합니다.
정 수 는 최대 상한 선 이 있다.대수 란 정수 최대 상한 선 을 넘 는 수 다.두 개의 큰 수의 구 화 문 제 를 해결 하기 위해 서 는 두 개의 큰 수 를 숫자 문자열 로 삼 아 이 수의 해당 숫자 를 두 개의 스 택 에 저장 하고 두 개의 스 택 에서 해당 하 는 비트 의 숫자 를 꺼 내 순서대로 덧셈 을 실행 하면 풀이 할 수 있다.
//       ,               (         )
//               

/**
 *          ,      :
 * (1)                    sA sB ;
 * (2)         ,              ,     partialSum ;
 *      ,           sum ,                 ;
 *       ,          sum ;
 * (3)         ,                      ,
 *          sum ,        。       ,    1   sum ;
 * (4)         ,  sum          。             。
 */
public class Example3_2 {
    public String add(String a, String b) throws Exception{
        LinkStack sum = new LinkStack();    //    
        LinkStack sA = numSplit(a);         //                 
        LinkStack sB = numSplit(b);         //                  
        int partialSum;                     //        
        boolean isCarry = false;            //    
        while(! sA.isEmpty() && !sB.isEmpty()){    //           
            partialSum = (Integer)sA.pop() + (Integer)sB.pop();  //       ,                
            if (isCarry){                   //    
                partialSum++;               //       
                isCarry = false;            //      
            }
            if (partialSum >= 10){          //    
                partialSum -= 10;
                sum.push(partialSum);
                isCarry = true;             //    
            }
            else {                          //       
                sum.push(partialSum);       //     
            }
        }

        LinkStack temp = !sA.isEmpty() ? sA: sB;    //              
        while(!temp.isEmpty()){
            if (isCarry){                           //               
                int t = (Integer)temp.pop();        //              
                ++t;    //       
                if (t >= 10){                       //    
                    t -= 10;
                    sum.push(t);
                }
                else {
                    sum.push(t);
                    isCarry = false;                 //      
                }
            }
            else    //                
                sum.push(temp.pop());    //                
        }
        if (isCarry){     //       
            sum.push(1);    //      
        }
        String str = new String();
        while(!sum.isEmpty())    //           
            str = str.concat(sum.pop().toString());
        return str;
    }

    //               ,         ,            
    public LinkStack numSplit(String str) throws Exception{
        LinkStack s = new LinkStack();
        for (int i = 0; i < str.length(); i++){
            char c = str.charAt(i);    //      char 
            if (' ' == c)
                continue;
            else if ('0' <= c && '9' >= c)    //      
                s.push(Integer.valueOf(String.valueOf(c)));
            else
                throw new Exception("  :         !");
        }
        return s;
    }
    public static void main(String[] args) throws Exception{
        Example3_2 e = new Example3_2();
        System.out.println("       :" + e.add("18 452 543 389 943 209 752 345 473", "8 123 542 678 432 986 899 334"));
    }
}


순서 스 택 에 관 한 코드 는 모두 스 택 이 글 에 있 습 니 다.

좋은 웹페이지 즐겨찾기