美文网首页
数据结构-栈(实现简单的数学运算)

数据结构-栈(实现简单的数学运算)

作者: 今年花开正美 | 来源:发表于2020-06-16 23:04 被阅读0次

    今天学习一个简单的数据结构知识:栈,并使用栈来实现简单的四则运算。

    栈介绍

    栈可以理解成先进后出的队列,最容易理解的例子就是我们堆盘子的过程了。栈是一种操作受限的线性结构,只允许在一端插入和取出元素,不允许从中间或另一端取出元素。
    栈的实现也是比较简单的,只要提供入栈、出栈方法即可,另外可以额外提供获得栈的长度以及判断是否为空方法。
    其次,为了实现遍历栈,需要实现Iterable接口。

    代码如下:

    public class Stack<Item> implements Iterable<Item> {
    
        private Node head;
        private int N;
    
        private class Node {
            Item item;
            Node next;
        }
    
        public Stack() {
        }
    
        public Item pop() {
            if (head != null) {
                Item item = head.item;
                head = head.next;
                N--;
                return item;
            }
            return null;
        }
    
        public void push(Item item) {
            Node oldHead = head;
            head = new Node();
            head.item = item;
            head.next = oldHead;
            N++;
        }
    
        public int size() {
            return N;
        }
    
        public boolean isEmpty() {
            return N == 0;
        }
    
        @Override
        public Iterator<Item> iterator() {
            return new ListIterator();
        }
    
        private class ListIterator implements Iterator {
            private Node current = head;
            private int i = N;
    
            @Override
            public boolean hasNext() {
                return i > 0;
            }
    
            @Override
            public Item next() {
                Item item = current.item;
                current = current.next;
                i--;
                return item;
            }
    
            @Override
            public void remove() {
                throw new UnsupportedOperationException();
            }
        }
    
       
    
    }
    
    

    实现简单数学运算

    使用栈来实现简单的加减乘除以及开根号运算是比较常见的场景。简单来说,我们需要维护两个栈。遍历输入的表达式,若为数字则加入到数字栈中。若为运算符,则从数字栈中取出一个或两个数字进行计算,然后再将结果存放到数字栈中。
    以此类推,最终遍历完表达式后数字栈中只会有一个数字,也就是结果了。

    代码如下:

    public class Evaluate {
        public static void main(String[] args) {
            Stack<String> ops = new Stack<>();
            Stack<Double> vals = new Stack<>();
            while (!StdIn.isEmpty()) {
                String s = StdIn.readString();
                if (s.equals("(")) ;
                else if (s.equals("+")
                        || s.equals("-")
                        || s.equals("*")
                        || s.equals("/")
                        || s.equals("sqrt")
                ) {
                    ops.push(s);
                } else if (s.equals(")")) {
                    String op = ops.pop();
                    Double v = vals.pop();
                    if (op.equals("+")) {
                        v = vals.pop() + v;
                    } else if (op.equals("-")) {
                        v = vals.pop() - v;
                    } else if (op.equals("*")) {
                        v = vals.pop() * v;
                    } else if (op.equals("*")) {
                        v = vals.pop() / v;
                    } else {
                        v = Math.sqrt(v);
                    }
                    vals.push(v);
                } else {
                    vals.push(Double.valueOf(s));
                }
            }
            StdOut.println("result is : " + vals.pop());
        }
    }
    

    算法相关实现源码地址:https://github.com/xiekq/rubs-algorithms

    相关文章

      网友评论

          本文标题:数据结构-栈(实现简单的数学运算)

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