java 实现 stack

   <p>栈是限制插入和删除只能在一个位置上进行的 List，该位置是 List 的末端，叫做栈的顶(top)，对于栈的基本操作有 push 和 pop，前者是插入，后者是删除。</p>    <p>栈也是 FIFO 表。</p>    <p>栈的实现有两种，一种是使用数组，一种是使用链表。</p>    <pre>  <code class="language-java">public class MyArrayStack<E> {     private ArrayList<E> list = new ArrayList<>();     public void push(E e) {    list.add(e);   }     public E pop() {    return list.remove(list.size() - 1);   }     public E peek() {    return list.get(list.size() - 1);   }     public boolean isEmpty() {    return list.size() == 0;   }  }    public class MyLinkStack<E> {     LinkedList<E> list = new LinkedList<>();     public void push(E e) {    list.addLast(e);   }     public E pop() {    return list.removeLast();   }     public E peek() {    return list.getLast();   }     public boolean isEmpty() {    return list.size() == 0;   }  }</code></pre>    <h2><strong>栈的应用</strong></h2>    <h3><strong>平衡符号</strong></h3>    <p>给定一串代码，我们检查这段代码当中的括号是否符合语法。</p>    <p>例如：[{()}] 这样是合法的，但是 [{]}() 就是不合法的。</p>    <p>如下是测试代码：</p>    <pre>  <code class="language-java">public class BalanceSymbol {     public boolean isBalance(String string) {    MyArrayStack<Character> stack = new MyArrayStack<>();    char[] array = string.toCharArray();    for (char ch : array) {     if ("{[(".indexOf(ch) >= 0) {      stack.push(ch);     } else if ("}])".indexOf(ch) >= 0) {      if (isMatching(stack.peek(), ch)) {       stack.pop();      }     }    }      return stack.isEmpty();   }     private boolean isMatching(char peek, char ch) {    if ((peek == '{' && ch == '}') || (peek == '[' && ch == ']') || (peek == '(' && ch == ')')) {     return true;    }    return false;   }     public static void main(String[] args) {    BalanceSymbol symbol = new BalanceSymbol();    String string = "public static void main(String[] args) {BalanceSymbol symbol = new BalanceSymbol();}";    String string2 = "public static void main(String[] args) {BalanceSymbol symbol = new BalanceSymbol([);}]";    System.out.println(symbol.isBalance(string));    System.out.println(symbol.isBalance(string2));   }  }</code></pre>    <h3><strong>后缀表达式</strong></h3>    <p>例如一个如下输入，算出相应的结果，</p>    <p>3 + 2 + 3 * 2 = ?</p>    <p>这个在计算顺序上不同会产生不同的结果，如果从左到右计算结果是 16，如果按照数学优先级计算结果是 11。</p>    <p>如果把上述的中缀表达式转换成后缀表达式：</p>    <p>3 2 + 3 2 * +</p>    <p>如果使用后缀表达式来计算这个表达式的值就会非常简单，只需要使用一个栈。</p>    <p>每当遇到数字的时候，把数字入栈。</p>    <p>每当遇到操作符，弹出2个元素根据操作符计算后，入栈。</p>    <p>最终弹出栈的唯一元素就是计算结果。</p>    <pre>  <code class="language-java">/**   * 简化版本，每个操作数只一位，并且假设字符串合法   */  public class PostfixExpression {     public static int calculate(String string) {    MyArrayStack<String> stack = new MyArrayStack<>();      char[] arr = string.toCharArray();      for (char ch : arr) {     if ("0123456789".indexOf(ch) >= 0) {      stack.push(ch + "");     } else if ("+-*/".indexOf(ch) >= 0) {      int a = Integer.parseInt(stack.pop());      int b = Integer.parseInt(stack.pop());      if (ch == '+') {       stack.push((a + b) + "");      } else if (ch == '-') {       stack.push((a - b) + "");      } else if (ch == '*') {       stack.push((a * b) + "");      } else if (ch == '/') {       stack.push((a / b) + "");      }     }    }    return Integer.parseInt(stack.peek());   }     public static void main(String[] args) {    System.out.println(calculate("32+32*+"));   }  }</code></pre>    <h3><strong>中缀表达式转换成后缀表达式</strong></h3>    <p>假设只运行 +，-，*，/，() 这几种表达式。并且表达式合法。</p>    <p>a + b * c - (d * e + f) / g 转换后的后缀表达式如下：</p>    <p>a b c * + d e * f + g / -</p>    <p>使用栈中缀转后缀步骤如下：</p>    <ul>     <li> <p>当读到操作数立即把它输出</p> </li>     <li> <p>如果遇到操作符入栈，如果遇到的左括号也放到栈中</p> </li>     <li> <p>如果遇到右括号，就开始弹出栈元素，直到遇到对应的左括号，左括号只弹出不输出。</p> </li>     <li> <p>如果遇到其他符号，那么从栈中弹出栈元素知道发现优先级更低的元素为止。</p> </li>    </ul>    <pre>  <code class="language-java">import java.util.HashMap;  import java.util.Map;    public class ExpressionSwitch {     private static Map<Character, Integer> map = new HashMap<Character, Integer>();     static {    map.put('+', 0);    map.put('-', 1);    map.put('*', 2);    map.put('/', 3);    map.put('(', 4);   }     private static char[][] priority = {     // 当前操作符     //        +    -    *    /    (      /* 栈 + */{ '>', '>', '<', '<', '<'},     /* 顶 - */{ '>', '>', '<', '<', '<'},     /* 操 * */{ '>', '>', '>', '>', '<'},     /* 作 / */{ '>', '>', '>', '>', '<'},           /* 符 ( */{ '<', '<', '<', '<', '<'},   };     public static String switch1(String string) {    StringBuilder builder = new StringBuilder();      char[] arr = string.toCharArray();      MyArrayStack<Character> stack = new MyArrayStack<>();    for (char ch : arr) {     if ("0123456789abcdefghijklmnopqrstuvwxyz".indexOf(ch) >= 0) {      builder.append(ch);     } else if ('(' == ch) {      stack.push(ch);     } else if (')' == ch) {      while (true && !stack.isEmpty()) {       char tmp = stack.pop();       if (tmp == '(') {        break;       } else {        builder.append(tmp);       }      }     } else {      while (true) {       if (stack.isEmpty()) {        stack.push(ch);        break;       }       char tmp = stack.peek();       if (isPriorityHigh(tmp, ch)) {        builder.append(stack.pop());       } else {        stack.push(ch);        break;       }      }     }    }      while(!stack.isEmpty()) {     builder.append(stack.pop());    }      return builder.toString();   }     private static boolean isPriorityHigh(char tmp, char ch) {    return priority[map.get(tmp)][map.get(ch)] == '>';   }     public static void main(String[] args) {    System.out.println(switch1("a+b*c-(d*e+f)/g"));   }  }</code></pre>    <p> </p>    <p> </p>    <p>来自：http://renchx.com/java-stack</p>    <p> </p>