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

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

栈介绍

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