定义了三个内部类（是自定义数组对象，栈接口，栈的实现）
如果不想用我实现的数组和栈，也可以导入java自带包（import java.util.Stack;）此时请直接看倒数第二个函数
public class Solution {
public class Array<E> {
private E[] data;
private int capacity;
private int size;
// 构造函数，传入数组的容量capacity构造Array
public Array(int capacity){
data = (E[]) new Object[capacity];
size = 0;
}
//无参的构造函数，默认数组的容量capacity=10
public Array(){
this(10);
}
//获取数组中的元素个数
public int getSize(){
return size;
}
//获取数组的容量
public int getCapacity(){
return capacity;
}
//返回数组是否为空
public boolean isEmpty(){
return size == 0;
}
//向所有元素后添加一个新元素
public void addLast(E e){
add(size, e);
}
//在所有元素前添加一个新元素
public void addFirst(E e){
add(0, e);
}
//在第index个位置插入一个新的元素e
public void add(int index, E e){
if(index < 0 || index > size){
throw new IllegalArgumentException("AddList failed. Require index >=0 and index <= size!");
}
if(size == data.length){
// throw new IllegalArgumentException("AddList failed. Arrat is full!");
// System.out.println(size);
// System.out.println(data.length);
resize(2*data.length);
}
for(int i = size -1; i>= index; i--){
data[i+1] = data[i];
}
data[index] = e;
size ++;
}
//获取index索引位置的元素
E get(int index){
if(index < 0 || index > size){
throw new IllegalArgumentException("Get failed. Index is illegal!");
}
return data[index];
}
//修改index索引位置的元素
void set(int index, E e){
if(index < 0 || index > size){
throw new IllegalArgumentException("Get failed. Index is illegal!");
}
data[index] = e;
}
//查找数组中是否有元素e
public boolean contains(E e){
for (int i=0; i<size; i++){
if(e.equals(data[i])){
return true;
}
}
return false;
}
//查找数组中元素e所在的索引，如果不存在元素e，则返回-1
public int find(E e){
for (int i=0; i<size; i++){
if(e.equals(data[i])){
return i;
}
}
return -1;
}
public E getLast(){
return get(size -1);
}
public E getFirst(){
return get(0);
}
//从数组中删除index位置的元素，返回删除的元素
public E remove(int index){
if(index<0 || index >=size){
throw new IllegalArgumentException("Remove failed. Index is illegal");
}
E ret = data[index];
for(int i=index+1; i<size ;i++){
data[i-1] = data[i];
}
size--;
data[size] = null;
if(size == data.length/4 && data.length/2 != 0){
resize(data.length/2);
}
return ret;
}
//从数组中删除第一个元素，返回删除的元素
public E removeFirst(){
return remove(0);
}
//从数组中删除第一个元素，返回删除的元素
public E removeLast(){
return remove(size-1);
}
//从数组中删除某个元素
public void removeElement(E e){
int index = find(e);
if(index != -1){
E ret = remove(index);
}
}
//从数组中删除所有元素
public void removeAllElement(E e){
int index = find(e);
if(index != -1){
E ret = remove(index);
removeAllElement(e);
}
}
@Override
public String toString(){
StringBuilder res = new StringBuilder();
res.append(String.format("Arrat: size = %d, capacity = %d\n",size,data.length));
res.append("[");
for (int i=0; i<size; i++){
res.append(data[i]);
if (i != size-1){
res.append(",");
}
}
res.append("]");
return res.toString();
}
private void resize(int newCapacity){
E[] newData = (E[]) new Object[newCapacity];
for(int i=0; i<size; i++){
newData[i] = data[i];
}
data = newData;
}
}
public interface Stack<E> {
int getSize();
boolean isEmpty();
void push(E e);
E pop();
E peek();
}
public class ArrayStack<E> implements Stack<E> {
Array<E> array;
public ArrayStack(int capacity){
array = new Array<>(capacity);
}
public ArrayStack(){
array = new Array<>();
}
@Override
public int getSize() {
return array.getSize();
}
@Override
public boolean isEmpty() {
return array.isEmpty();
}
@Override
public void push(E e) {
array.addLast(e);
}
@Override
public E pop() {
return array.removeLast();
}
@Override
public E peek() {
return array.getLast();
}
public int getCapacity(){
return array.getCapacity();
}
@Override
public String toString(){
StringBuilder res = new StringBuilder();
res.append("Stack: ");
res.append("[");
for (int i=0; i<array.getSize(); i++){
res.append(array.get(i));
if(i != array.getSize()-1){
res.append(", ");
}
}
res.append("] top");
return res.toString();
}
}
public boolean isValid(String s) {
ArrayStack<Character> stack = new ArrayStack<>();
for(int i=0; i<s.length(); i++){
char c = s.charAt(i);
if(c =='(' || c=='[' || c=='{'){
stack.push(c);
}else{
if(stack.isEmpty()){
return false;
}
char topChar = stack.pop();
if(c== ')' && topChar != '('){
return false;
}
if(c== ']' && topChar != '['){
return false;
}
if(c== '}' && topChar != '{'){
return false;
}
}
}
return stack.isEmpty();
}
public static void main(String[] args) {
System.out.println(new Solution().isValid("(())"));
}
}