List实现栈结构，应用于波兰算法-白红宇的个人博客

发布日期：2021-05-09 09:33:48 浏览次数：22 分类：博客文章

本文共 6682 字，大约阅读时间需要 22 分钟。

栈是一种执行“后进先出”算法的数据结构,栈的特点是先进后出。

我们使用java中的List集合实现一个栈数据结构。

package com.prolog.api.webservicetest;/* * @auther 顶风少年 * @mail dfsn19970313@foxmail.com * @date 2020-01-02 11:41 * @notify * @version 1.0 */import java.util.ArrayList;import java.util.Arrays;import java.util.List;public class Stack {    private ArrayList
      
        stackList = new ArrayList<>();    //添加元素到栈顶    public void add(String... integers) {        List
       
         integers1 = Arrays.asList(integers);        stackList.addAll(integers1);    }    //弹出栈顶元素    public String popup() {        if (stackList.size() == 0) {            return "-1";        }        return stackList.remove(stackList.size() - 1);    }    //返回栈顶元素，不是弹出    public String getTop() {        if (stackList.size() == 0) {            return "-1";        }        return stackList.get(stackList.size() - 1);    }    //判断栈是否为空    public boolean isEmpty() {        return stackList.isEmpty();    }    //返回栈内元素个数    public Integer getSize() {        return stackList.size();    }    //清空栈    public void clearStack() {        stackList.clear();    }}

View Code

需要注意的是，弹栈和获取栈顶元素时，需要判断栈内是否有元素，否则会抛出异常。

栈的应用

问题：设括号必须成对出现。

1 循环字符串

2 如果元素是（则压栈

3 如果元素是）判断当前栈内有没有元素，如果没有则不合法

4 如果有那只可能是（则弹出，抵消。

5 当循环结束，如果栈内没有元素则字符串合法

@Test    public void t1() throws Exception {        Stack stack = new Stack();        String str = "(a+b)*(a-c)";        for (int i = 0; i < str.length(); i++) {            String s = String.valueOf(str.charAt(i));            if (s.equals("(")) {                stack.add(s);            } else if (s.equals(")")) {                if (stack.isEmpty()) {                    System.out.println("字符串不合法");                    return;                } else {                    stack.popup();                }            }        }        if (stack.isEmpty()) {            System.out.println("字符串合法");        } else {            System.out.println("字符串不合法");        }    }

View Code

问题：中缀表达式转换后缀表达式

在计算3+2时，

CPU从内存中得到指令将3放入寄存器，然后在将2放入计算器，最后使用运算器算出3-2的值返回给内存。

指令3+2最终形成的格式就是 3 2 + 而这种格式也成为波兰表达式

将中缀表达式转成后缀表达式的规则，其实就是按照计算顺序，假装计算完毕，将运算符放到结果后。

计算波兰表达式（后缀表达式）

中缀表达式 9+(3-1)*3+10/2 = 20

9+（31-）*3+10/2

9+ 31-3* + 10/2

9+ 31-3* + 102/

931-3*+ + 102/

931-3*+102/+

转换

后缀表达式 9 3 1-3*+ 10 2/+

1 循环字符串，如果是数字，则添加到字符串缓冲区

2 如果是（则压栈

3 如果是）则持续弹栈，将弹出的元素添加到缓冲区，直到遇到（但是（不添加到缓冲区

4 如果是 + - * / 则获取栈顶元素，如果是空栈则压栈，如果不是空栈，则判断栈顶元素是否是 + - * /

如果是则判断当前字符串的优先级和栈顶运算符的优先级。如果大于栈顶运算符优先级则压栈，如果小于

或等于栈顶运算符优先级，则弹栈，将弹出的将运算符添加到缓冲区。此时需要继续判断栈顶元素是否是运算符，如果是，则重复执行步骤4,

5 当字符串循环结束，栈内可能还有元素，则将其全部弹出，添加到缓冲区

@Test    public void t3() {        //中缀表达式 4+2*（6/2)-3        //后缀表达式 4262/*+3-        Stack stack = new Stack();        String[] str = {"4", "+", "2", "*", "(", "6", "/", "2", ")", "-", "3"};        StringBuilder sb = new StringBuilder();        for (String s : str) {            try {                Integer integer = Integer.valueOf(s);                sb.append(integer);            } catch (Exception e) {                if (s.equals("(")) {                    stack.add(s);                } else if (s.equals(")")) {                    while (true) {                        String popup = (String) stack.popup();                        if (popup.equals("(")) {                            break;                        } else {                            sb.append(popup);                        }                    }                } else {                    if (!stack.isEmpty()) {                        String top = (String) stack.getTop();                        if (top.equals("+") || top.equals("-") || top.equals("*") || top.equals("/")) {                            boolean compare = compare(s, top);                            if (compare) {                                stack.add(s);                            } else {                                while (true) {                                    String popup = (String) stack.popup();                                    sb.append(popup);                                    String top1 = (String) stack.getTop();                                    if (!(top.equals("+") || top.equals("-") || top.equals("*") || top.equals("/"))) {                                        break;                                    }                                    if (top1.equals("-1") || compare(s, top1)) {                                        break;                                    }                                }                            }                        } else {                            stack.add(s);                        }                    } else {                        stack.add(s);                    }                }            }        }        while (true) {            String s = (String) stack.popup();            sb.append(s);            if (s.equals("-1")) {                break;            }        }        System.out.println(sb.toString());    }    //s1 大于 s2 返回 true    public boolean compare(String s1, String s2) {        Map
      
        map = new HashMap<>();        map.put("+", 1);        map.put("-", 1);        map.put("*", 2);        map.put("/", 2);        Integer s1c = map.get(s1);        Integer s2c = map.get(s2);        if (s1c > s2c) {            return true;        } else {            return false;        }    }

View Code

问题：计算后缀表达式

1 循环字符串，如果是数字则压栈

2 如果是 + - * / 运算符，则连续弹出栈顶的两个元素

3 把第二次弹出的元素和第一次弹出的元素运算。切记不要搞混了顺序。运算结束后，将结果压栈。

4 最终栈内的值就是运算结果。

@Test    public void t2() {        //中缀表达式 9+(3-1)*3+10/2 = 20        //后缀表达式 9 3 1-3*+ 10 2/+        //中缀表达式 6*(4+4*8)/2+3 = 111        //后缀表达式 6448*++*2/3+        //中缀表达式 4+2*（6/2)-3 = 7        //后缀表达式 4262/*+3-        Stack stack = new Stack();        //String[] str = {"9", "3", "1", "-", "3", "*", "+", "10", "2", "/", "+"};        //String[] str = {"6", "4", "4", "8", "*", "+", "*", "2", "/", "3", "+"};        String[] str = {"4", "2", "6", "2", "/", "*", "+", "3", "-"};        for (String s : str) {            try {                Integer integer = Integer.valueOf(s);                stack.add(integer);            } catch (Exception e) {                Integer a = (Integer) stack.popup();                Integer b = (Integer) stack.popup();                switch (s) {                    case "+":                        stack.add(b + a);                        break;                    case "-":                        stack.add(b - a);                        break;                    case "*":                        stack.add(b * a);                        break;                    case "/":                        stack.add(b / a);                        break;                }            }        }        System.out.println(stack.popup());    }

View Code

上一篇：List实现队列--杀人游戏

下一篇：mybatis

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

栈的应用

问题：设括号必须成对出现。

问题：中缀表达式转换后缀表达式

问题：计算后缀表达式

发表评论

最新留言

关于作者

推荐文章