ID #12678

Java实现基于栈实现整数加法算法

整数是有最大上限的,如果整数超出最大上限位数,如 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;

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;
         } else {
           result.push(sum - 10);
           addition = 1;
         }
       }else if (!oper2.empty()){
         int sum = oper2.pop() + addition;
         if (sum < 10) {
           result.push(sum);
           addition = 0;
         } else {
           result.push(sum - 10);
           addition = 1;
         }
       }else {
         result.push(1);
         addition = 0;
       }
     }
     while (!oper1.empty())
       result.push(oper1.pop());
     while (!oper2.empty())
       result.push(oper2.pop());
   }
   public void printResult() {
     System.out.print("Operator1:" + soper1 + '\n');
     System.out.print("Operator2:" + soper2 + '\n');
     System.out.print("Result  :");
     while (result.empty() == false)
       System.out.print(result.pop());
     System.out.println();
   }
   public static void main(String[] args) {
     IntStack int1 = new IntStack();
     IntStack int2 = new IntStack();
     StackOper so = new StackOper(int1, int2);
     so.pushNum("1313", "19");
     so.add();
     so.printResult();
   }
}


2011-07-02 11:27
阅读:
I'm VC , Just U know Y
本站部分文章来源于互联网,版权归原作者所有。

延伸阅读:

用Java程序编写记事本

不用spring,hibernate超傻瓜JAVA开发(javabean+数组)

用Java编写计算器的几种常见的做法

proxool.default (HouseKeeper.java:149)异常解决办法

九大因素让Java EE 6成为你的省钱法宝