美文网首页
数据结构和算法四(栈的经典应用逆波兰表达式的运用)

数据结构和算法四(栈的经典应用逆波兰表达式的运用)

作者: 小窦子 | 来源:发表于2017-11-11 23:23 被阅读0次

    思路

    数字输出,运算符进栈,括号匹配出栈,栈顶优先级出栈
    a、首先使用两个栈 一个是s1 一个是s2 s1 是用来临时存储运算符的, s2 是用来存放输入的逆波兰表达式的,
    b、从中缀表达式的最左端开始,逐个读取每一个字符,如果操作数,则压入s2,如果是左括号,则压入s1,如果为右括号,则将s1中的运算符依次取出并且压入s2,直到遇到左括号,但是该左括号出栈 但不压入s2,如果为操作符, 判断s1是否为空,如果为空 则将它压入s2,如果扫描到的比栈顶的元素的优先级大 将它入栈,如果扫描到的比小于栈顶或者等于栈顶的优先级小,直到扫描到的元素大于栈顶的元素(注意这里是一个循环),然后判断s1里面如果还有运算符 则一一出栈压入到s2中
    c、然后这个时候所有的数据全部在s2中,这个时候从的将s2逆置,从栈底开始取元素,开始扫描,如果扫描到的是一个运算符,则将他之前扫描到的两个元素做运算,得到存储到该位置,一直扫描,直到栈里还剩一个元素,就得到结果。

    代码实现

    自己写的 就是为了实现可能还有问题 大家可以提出来

      public class ReversePolishUtil {
      /**
        *是一个中缀表达式
        * @param express
        */
      public static void Reverse(String[] express) {
        if (express == null || express.length == 0) {
            抛出异常;
       }
        运来存放运算符
        StackDemo</a> s1 = new StackDemo ();
        用来存放输入逆波兰表达式
        StackDemo s2 = new StackDemo ();
        依次遍历这个数组
        for (int i = 0; i < express.length; i++) {
              String nowChar = express[i];
              Pattern pattern = Pattern.compile("[0-9]*");
              boolean isMacth = pattern.matcher(nowChar).matches();
              if (isMacth) {
              如果是数字 直接压入s2
              s2.push(nowChar);
              } else {
              否则就是操作符 就得判断s1 栈顶的元素
              if (s1.empty()) {
              如果为空 直接push
              s1.push(nowChar);
              } else if (nowChar.equals("(")) {
              如果是左括号 直接push s1
                s1.push(nowChar);
              } else if (nowChar.equals(")")) {
              如果是右括号, s1中的运算符依次出栈 压入到s2中, 直到遇到左括号, 但是左括号是直接出栈的
                  while (!s1.empty() && !s1.peek().equals("(")) {
                            s2.push(s1.pop());
                          }
                  然后将左括号也给出栈
                  s1.pop();
              } else if (nowChar.equals("+") || nowChar.equals("-")) {
              1、如果扫描到的比栈顶的元素的优先级大 将它入栈
              2、如果扫描到的比小于栈顶或者等于栈顶的优先级小,知道扫描到的元素大于栈顶的元素扫描到的运算符
                   while (!s1.empty() && !s1.peek().equals("(")) {
                在这里只要不遇到左括号 就一直出栈,因为优先级都比它大
                            s2.push(s1.pop());
                           }
              在这里是要么遇到括号 要么s1出栈为null了
                    s1.push(nowChar);
              } else if (nowChar.equals("*") || nowChar.equals("/")) {
              在这里一直出栈的情况是只有当遇到 * 和/
                    while (!s1.empty() && s1.peek().equals("*") || s1.peek().equals("?")) {
                             s2.push(s1.pop());//出栈
                          }
                    s1.push(nowChar);
              }
          }
        如果s1里面还有操作符 则push到s2里面
        while (!s1.empty()) {
              s2.push(s1.pop());
        }
      while (!s2.empty()) {
        Log.e("Reverse", s2.pop() + "");
        }  
      }
    }
    

    然后使用数组手写一个栈,上面的逆波兰就用的这个demo

        public class StackDemo {
        //初始数组的大小
        private int capacity = 3;
        //数组中元素的个数
        private int size = 0;
        //由于是数组设计到扩容 ,这里直接是扩容1.5倍
        private int increment = 2;
        private Object[] elementData = new Object[capacity];
        public StackDemo() {
        }
    
        public StackDemo(int capacity) {
        this.capacity = capacity;
        }
        //实现一个push的方法
        public void push(Object obj) {
        //在这里要判断是否超出了 如果超过了就得扩容 注意相等也要判断 坑了
          if (size >= elementData.length) {      
            grow(); //扩容
            }
        elementData[size] = obj;
        size++;
        }
    
        //移除栈顶的元素
        public Object pop() {
            if (elementData == null || elementData.length == 0 || size == 0) {
                return "";
            }
            size--;
            return elementData[size];
        }
        public boolean empty() {
            if (elementData == null || elementData.length == 0 || size == 0) {
                return true;
            }
            return false;
        }
        /**
         * 查看栈顶元素但是不删除
         * @return
         */
        public Object peek() {
            if (elementData == null || elementData.length == 0 || size == 0) {
                return "";
            }
            return elementData[size - 1];
        }
        //数组大小的扩容
        private void grow() {
            int newcapacity = (increment * elementData.length);
            elementData = Arrays.copyOf(elementData, newcapacity);
        }
    

    }

    最后调用:
    String[] string = {"12", "+", "4", "+", "5","*","(","3","-","2",")"};
    ReversePolishUtil.Reverse(string); 吧上一篇文章的结果打印出来是没问题的

    相关文章

      网友评论

          本文标题:数据结构和算法四(栈的经典应用逆波兰表达式的运用)

          本文链接:https://www.haomeiwen.com/subject/bjggmxtx.html