스 택 에서 대수 덧셈 문제 해결 (자바 구현)
16676 단어 데이터 구조
정 수 는 최대 상한 선 이 있다.대수 란 정수 최대 상한 선 을 넘 는 수 다.두 개의 큰 수의 구 화 문 제 를 해결 하기 위해 서 는 두 개의 큰 수 를 숫자 문자열 로 삼 아 이 수의 해당 숫자 를 두 개의 스 택 에 저장 하고 두 개의 스 택 에서 해당 하 는 비트 의 숫자 를 꺼 내 순서대로 덧셈 을 실행 하면 풀이 할 수 있다.
// , ( )
//
/**
* , :
* (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"));
}
}
순서 스 택 에 관 한 코드 는 모두 스 택 이 글 에 있 습 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.