今天学习一个简单的数据结构知识:栈,并使用栈来实现简单的四则运算。
栈介绍
栈可以理解成先进后出的队列,最容易理解的例子就是我们堆盘子的过程了。栈是一种操作受限的线性结构,只允许在一端插入和取出元素,不允许从中间或另一端取出元素。
栈的实现也是比较简单的,只要提供入栈、出栈方法即可,另外可以额外提供获得栈的长度以及判断是否为空方法。
其次,为了实现遍历栈,需要实现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
网友评论