<?php

require '../array/ArrayList.php';
/**
 * Class Stack
 * 实现栈、
 * 可以继承 ArrayList 类
 * 接口设计
 * @size() 元素的数量
 * @isEmpty() 是否为空
 * @push(item) 入栈
 * @pop() 出栈
 * @top() 获取栈顶元素
 * @clear() 清空栈元素
 */
class Stack
{
    private $arrayList=null;
    public function __construct()
    {
        // 代理类
        $this->arrayList = new ArrayList();
    }

    public function size() : int
    {
        return $this->arrayList->getSize();
    }

    public function isEmpty(){
        return $this->arrayList->isEmpty();
    }

    public function push($item):void
    {
        $this->arrayList->add($item);
    }

    public function pop()
    {
        return $this->arrayList->remove($this->arrayList->getSize()-1);
    }

    public function top(){
        return $this->arrayList->get($this->arrayList->getSize()-1);
    }

    public function clear():void
    {
        $this->arrayList->clear();
    }

    public function __toString():string
    {
        return  $this->arrayList->__toString();
    }
}
class Solution {

    protected static $solution = [
        '(' => ')',
        '{' => '}',
        '[' => ']'
    ];
    /**
     * 题目来源力扣
     * https://leetcode-cn.com/problems/valid-parentheses/
     * 判断是否是有效的括号
     * @param String $s
     * @return Boolean
     */
    public function isValid($s) {
        $stack = new Stack();
        $len = strlen($s);
        for($i=0;$i<$len;$i++){
            $char = $s[$i];
            // 第二版优化
            if (in_array($char,array_keys(self::$solution))){
                $stack->push($char);
            }else{
                if($stack->isEmpty()) return false;
                $left = $stack->pop();
                if($char !== self::$solution[$left]) return false;
            }
            // 第一版
//            if('(' === $char || '{' === $char || '[' === $char){
//                // 入栈。左字符进行入栈，为什么是左字符，如果第一个是右字符的话，那肯定不是有效的括号
//                $stack->push($char);
//            } else{
//                if($stack->isEmpty()) return false;
//                $left = $stack->pop();
//
//                if('(' === $left && ')' !== $char)return false;
//                if('{' === $left && '}' !== $char)return false;
//                if('[' === $left && ']' !== $char)return false;
//
//            }
        }
        return $stack->isEmpty();
    }
}
$stack = new Stack();
$stack->push(1);
$stack->push(2);
$stack->push(3);
//var_dump($stack->size());
$solution = new Solution();
$ret = $solution->isValid('([{]}])');
var_dump($ret);
//var_dump((string)$stack);