java 实现 stack详解及实例代码
栈是限制插入和删除只能在一个位置上进行的 List,该位置是 List 的末端,叫做栈的顶(top),对于栈的基本操作有 push 和 pop,前者是插入,后者是删除。 栈也是 FIFO 表。 栈的实现有两种,一种是使用数组,一种是使用链表。 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; } } 栈的应用 平衡符号 给定一串代码,我们检查这段代码当中的括号是否符合语法。 例如:[{()}] 这样是合法的,但是 [{]}() 就是不合法的。 如下是测试代码: 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)); } } 后缀表达式 例如一个如下输入,算出相应的结果, 3 + 2 + 3 * 2 = ? 这个在计算顺序上不同会产生不同的结果,如果从左到右计算结果是 16,如果按照数学优先级计算结果是 11。 如果把上述的中缀表达式转换成后缀表达式: 3 2 + 3 2 * + 如果使用后缀表达式来计算这个表达式的值就会非常简单,只需要使用一个栈。 每当遇到数字的时候,把数字入栈。 每当遇到操作符,弹出2个元素根据操作符计算后,入栈。 最终弹出栈的唯一元素就是计算结果。 /** * 简化版本,每个操作数只一位,并且假设字符串合法 */ 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*+")); } } 中缀表达式转换成后缀表达式 假设只运行 +,-,*,/,() 这几种表达式。并且表达式合法。 a + b * c - (d * e + f) / g 转换后的后缀表达式如下: a b c * + d e * f + g / - 使用栈中缀转后缀步骤如下:
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")); } } 通过此文,希望大家对Java stack 的知识掌握,谢谢大家对本站的支持! 您可能感兴趣的文章:
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |
- java – 有没有办法自动化junit bean属性测试?
- java web开发之购物车功能实现示例代码
- NoClassDefFoundError使用Jackson 2.2.x在Android上与Gradl
- java – 无法从Netbeans 8.0.1服务区域内启动GlassFish 4.1
- java – nextDouble()在输入double时抛出InputMismatchExce
- java – Spring和Hibernate突然将事务设置为只读
- java – FileOutputStream.close在写大文件时非常慢
- java – 我的Eclipse的包资源管理器中的白色包图标
- java – Hibernate条件使用GROUP BY和RETURN ENTITY LIST
- java之操作集合的工具类--Collections