Java实现基于栈实现整数加法算法
时间:2011-04-13
整数是有最大上限的,如果整数超出最大上限位数,如 4398912120931092319+49832232849329019019210921029,此时整型变量无法保存这些数字.解 决的办法是,可利用字符串保存这些数字,再利用栈做按位加法.
1.用Java实现,首先使用链表LinkedList构造栈数据结构.
import java.util.LinkedList;
public class IntStack {
private LinkedList<Integer> storage = new LinkedList<Integer> ();
/** 入栈 */
public void push(int v) {
storage.addFirst(v);
}
/** 出栈，但不删除 */
public int peek() {
return storage.getFirst();
}
/** 出栈 */
public int pop() {
return storage.removeFirst();
}
/** 栈是否为空 */
public boolean empty() {
return storage.isEmpty();
}
/** 打印栈元素 */
public String toString() {
return storage.toString();
}
}
2.使用栈加法操作.
2.1栈oper1和栈oper2分别保存两个加数,栈result保存结果;
2.2方法pushNum(String soper1, String soper2)将两个数字字符串分别保存于两个栈中 ;
2.3方法add()进行加法操作,具体算法是:
[1]整型变量addition保存一个十位值,只能取值0或1,两个9相加为18;
[2]循环从两个栈中取数据,将相加的结果的个位值保存于栈result,十位值保存于整型变 量addition;
[3]整型变量addition初始值为0,每次要参与下一轮运算;
[4]当某加数栈(栈oper1或栈oper2)为空后,直接将另一个栈的数据复制到栈result;
Java糞?児噐媚糞?屁方紗隈麻隈(2)
扮寂:2011-04-13
2.4 霞編,峇佩殻會補竃:
Operator1:1313
Operator2:19
Result :1332
public class StackOper {
private IntStack oper1;
private IntStack oper2;
private IntStack result;
private String soper1;
private String soper2;
public StackOper(IntStack stack1, IntStack stack2) {
oper1 = stack1;
oper2 = stack2;
result = new IntStack();
}
public void pushNum(String soper1, String soper2) {
this.soper1 = soper1;
this.soper2 = soper2;
push(soper1, oper1);
push(soper2, oper2);
}
private void push(String s, IntStack stack) {
char num[] = s.toCharArray();
for (int i = 0; i < num.length; i++) {
if (num[i] <= 57 && num[i] >= 48)
stack.push(num[i] - 48);
else
throw new UnsupportedOperationException("Not Digital");
}
}
public void add() {
int addition = 0;
while (!oper1.empty() && !oper2.empty()) {
int sum = oper1.pop() + oper2.pop() + addition;
if (sum < 10) {
result.push(sum);
addition = 0;
} else {
result.push(sum - 10);
addition = 1;
}
}
while (addition == 1) {
if (!oper1.empty()){
int sum = oper1.pop() + addition;
if (sum < 10) {
result.push(sum);
addition = 0;
} el
|
