Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1290994
  • 博文数量: 297
  • 博客积分: 285
  • 博客等级: 二等列兵
  • 技术积分: 3006
  • 用 户 组: 普通用户
  • 注册时间: 2010-03-06 22:04
个人简介

Linuxer, ex IBMer. GNU https://hmchzb19.github.io/

文章分类

全部博文(297)

文章存档

2020年(11)

2019年(15)

2018年(43)

2017年(79)

2016年(79)

2015年(58)

2014年(1)

2013年(8)

2012年(3)

分类: Java

2017-09-06 19:29:01

废话不多少,直接上代码。
前面还有个Stack的实现和用Stack解析数学表达式。
http://blog.chinaunix.net/uid-7713641-id-5761516.html


这是Stack的实现,代码出自Object-Oriented Data Structures Using Java.

点击(此处)折叠或打开

  1. package Algorithms;

  2. class StackUnderflowException extends RuntimeException{
  3.     //only 2 constructor
  4.     public StackUnderflowException(){
  5.         super();
  6.     }
  7.     public StackUnderflowException(String message){
  8.         super(message);
  9.     }
  10. }
  11. class StackOverflowException extends RuntimeException{
  12.     //only 2 constructor
  13.     public StackOverflowException(){
  14.         super();
  15.     }
  16.     public StackOverflowException(String message){
  17.         super(message);
  18.     }
  19. }

  20. interface StackInterface<T>{
  21.     void push(T element) throws StackOverflowException;
  22.     /* Throws StackOverflowException if this stack is full.
  23.     otherwise places element at the top of this stack.
  24.      */

  25.     void pop() throws StackUnderflowException;
  26.     //Throws StackUnderflowException if this stack is empty.
  27.     //otherwise removes top element from this stack.

  28.     T top() throws StackUnderflowException;
  29.     //Throws StackUnderflowException if this stack is empty.
  30.     //otherwise returns top element of this stack

  31.     boolean isFull();
  32.     //Returns true if this stack is full, otherwise returns false

  33.     boolean isEmpty();
  34.     //Returns true if this stack is empty, otherwise returns false.
  35. }

  36. class ArrayBoundedStack<T> implements StackInterface<T>{
  37.     //use Array implement a stack
  38.     protected final int DEFCAP = 100; //Default capacity
  39.     protected T[] elements; //holds stack element
  40.     protected int topIndex = -1; //index of top element in stack

  41.     public ArrayBoundedStack(){
  42.         elements = (T[]) new Object[DEFCAP];
  43.     }

  44.     public ArrayBoundedStack(int maxSize){
  45.         elements = (T[]) new Object[maxSize];
  46.     }

  47.     public boolean isEmpty(){
  48.         return (topIndex == -1);
  49.     }

  50.     public boolean isFull(){
  51.         return (topIndex == (elements.length-1));
  52.     }

  53.     public void push(T element){
  54.         if(isFull()){
  55.             throw new StackOverflowException("Push attempted on a full stack");
  56.         }else{
  57.             topIndex++;
  58.             elements[topIndex]=element;
  59.         }
  60.     }

  61.     public void pop(){
  62.         if(isEmpty()){
  63.             throw new StackUnderflowException("Pop attempted on a empty stack");
  64.         }else{
  65.             elements[topIndex]=null;
  66.             topIndex--;
  67.         }
  68.     }

  69.     public T top() {
  70.         T topOfStack = null;
  71.         if (isEmpty()) {
  72.             throw new StackUnderflowException("Top attempted on empty stack");
  73.         } else {
  74.             topOfStack = elements[topIndex];
  75.             return topOfStack;
  76.         }
  77.     }
  78. }

  79. public class MyStack {

  80.     public static void revStr(){
  81.         ArrayBoundedStack<String> stringStack;
  82.         stringStack = new ArrayBoundedStack<String>(3);
  83.         stringStack.push("1 Hero: Demon Hunter");
  84.         stringStack.push("2 Hero: Keeper of the Grove");
  85.         stringStack.push("3 Hero: Priestess of the Moon");

  86.         String line;
  87.         System.out.println("Reverse");
  88.         while(!stringStack.isEmpty()){
  89.             line=stringStack.top();
  90.             stringStack.pop();
  91.             System.out.println(line);
  92.         }
  93.     }

  94.     public static void main(String[] args) {
  95.         revStr();
  96.     }
  97. }
下面是用Java的ArrayList实现的Stack。好简单啊

点击(此处)折叠或打开

  1. public class MyArrayListStack<T> implements StackInterface<T> {
  2.     protected ArrayList<T> elements;
  3.     public MyArrayListStack() {
  4.         this.elements = new ArrayList<T>();
  5.     }

  6.     @Override
  7.     public void push(T element){
  8.         elements.add(element);
  9.     }

  10.     @Override
  11.     public void pop() throws StackUnderflowException {
  12.         if(isEmpty()){
  13.             throw new StackUnderflowException("Pop attempted on a empty stack");
  14.         }else{
  15.             elements.remove(elements.size()-1);
  16.         }
  17.     }

  18.     @Override
  19.     public T top() throws StackUnderflowException {
  20.         if(isEmpty()){
  21.             throw new StackUnderflowException("Top attempted on a empty stack");
  22.         }else{
  23.             T topOfStack = elements.get(elements.size()-1);
  24.             return topOfStack;
  25.         }
  26.     }

  27.     @Override
  28.     public boolean isFull() {
  29.         //ArrayList is never full
  30.         return false;
  31.     }

  32.     @Override
  33.     public boolean isEmpty() {
  34.         return elements.size() == 0 ;
  35.     }
  36. }
玩票性质的把LLNode写成了一个public 的InnerClass. 这是个单链表实现的Stack.

点击(此处)折叠或打开

  1. package Algorithms;

  2. public class MyLinkedStack<T> implements StackInterface<T> {
  3.     //Inner class LLNode
  4.     public class LLNode<T>{
  5.         private T info;
  6.         private LLNode<T> link;

  7.         public LLNode(T info) {
  8.             this.info = info;
  9.             this.link = null;
  10.         }

  11.         public void setInfo(T info){
  12.             this.info = info;
  13.         }

  14.         public T getInfo() {
  15.             return info;
  16.         }

  17.         public LLNode<T> getLink() {
  18.             return link;
  19.         }

  20.         public void setLink(LLNode<T> link) {
  21.             this.link = link;
  22.         }
  23.     }
  24.     //reference to the top
  25.     protected LLNode<T> top;

  26.     public MyLinkedStack(){
  27.         top=null;
  28.     }

  29.     public void push(T element){
  30.         LLNode<T> newNode = new LLNode<T>(element);
  31.         newNode.setLink(top);
  32.         top = newNode;
  33.     }

  34.     public void pop(){
  35.         if(isEmpty()){
  36.             throw new StackUnderflowException("Pop attempted on an empty stack.");
  37.         }else{
  38.             top = top.getLink();
  39.         }
  40.     }

  41.     public T top(){
  42.         if(isEmpty()){
  43.             throw new StackUnderflowException("Pop attempted on an empty stack.");
  44.         }else {
  45.             return top.getInfo();
  46.         }
  47.     }

  48.     public boolean isFull(){
  49.         //linked stack is never full
  50.         return false;
  51.     }

  52.     public boolean isEmpty(){
  53.         return (top == null);
  54.     }
  55. }


BalanceChecker类

点击(此处)折叠或打开

  1. package Algorithms;

  2. public class BalanceChecker {

  3.     protected String openSet;
  4.     protected String closeSet;

  5.     //constructor
  6.     public BalanceChecker(String openSet, String closeSet) {
  7.         //Preconditions: No character is contained more than once in the
  8.         // combined openSet and closeSet strings.
  9.         // The size of openSet = the size of closeSet.
  10.         this.openSet = openSet;
  11.         this.closeSet = closeSet;
  12.     }


  13.     public int test(String expression){
  14.         // Returns 0 if expression is balanced.
  15.         // Returns 1 if expression has unbalanced symbols.
  16.         // Returns 2 if expression came to end prematurely.
  17.         char currChar;
  18.         int currCharIndex;
  19.         int lastCharIndex;

  20.         int openIndex;
  21.         int closeIndex;

  22.         boolean stillBalanced=true;

  23.         StackInterface<Integer> stack;
  24.         stack = new ArrayBoundedStack<>(expression.length());

  25.         currCharIndex=0;
  26.         lastCharIndex= expression.length()-1;
  27.         while(stillBalanced && (currCharIndex <= lastCharIndex)){
  28.             currChar = expression.charAt(currCharIndex);
  29.             openIndex = openSet.indexOf(currChar);

  30.             if(openIndex != -1) {
  31.                 //current character not in openSet
  32.                 //push the current char onto the stack
  33.                 stack.push(openIndex);
  34.             }else{
  35.                 closeIndex = closeSet.indexOf(currChar);
  36.                 if(closeIndex != -1){ //current character in closeSet
  37.                     try{
  38.                         //try to pop an index off the stack
  39.                         openIndex = stack.top();
  40.                         stack.pop();
  41.                         if(openIndex != closeIndex){
  42.                             //not match, then not balanced
  43.                             stillBalanced = false;
  44.                         }
  45.                     }catch(StackUnderflowException e){
  46.                         // if stack was empty
  47.                         stillBalanced = false;
  48.                     }
  49.                 }
  50.             }
  51.             currCharIndex++;
  52.             //set up processing of next character
  53.         }
  54.         if(!stillBalanced){
  55.             //unbalanced symbols
  56.             return 1;
  57.         }else if(!stack.isEmpty()){
  58.             //premature end of expression
  59.             return 2;
  60.         }else{
  61.             //expression is balanced
  62.             return 0;
  63.         }
  64.     }
  65. }
测试代码:

点击(此处)折叠或打开

  1. package Algorithms;

  2. import java.util.Scanner;

  3. public class TestBalanceChecker {
  4.     public static void main(String[] args) {
  5.         BalanceChecker bc = new BalanceChecker("([{", ")]}");
  6.         Scanner sc = new Scanner(System.in);

  7.         //0=balanced, 1=unbalanced, 2 = premature end
  8.         int result;

  9.         String expresison = null;
  10.         final String STOP="X"; //Indicate the end of input

  11.         while(!STOP.equalsIgnoreCase(expresison)){
  12.             //Get next expression to be processed
  13.             System.out.println("Expression ("+STOP+ " to stop): ");
  14.             expresison = sc.nextLine();
  15.             if(!STOP.equalsIgnoreCase(expresison)){
  16.                 //Obtain and output result of balanced testing
  17.                 result= bc.test(expresison);
  18.                 if(result == 1){
  19.                     System.out.println("Unbalanced");
  20.                 }else if(result == 2){
  21.                     System.out.println("Premature end of expression ");
  22.                 }else{
  23.                     System.out.println("Balanced ");
  24.                 }
  25.             }
  26.         }
  27.     }
  28. }

阅读(587) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~