数据结构-PHP "栈" 结构匹配花括号有效性

码农天地 - 2020-10-20 11:49:34

这篇文章是展示如何使用栈(Stack)这种数据结构来匹配花括号有效性，首先抛出问题，这里直接贴出问题如下：

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
-------------------------------------------------
示例 1:
输入: "()"
输出: true
示例 2:

输入: "()[]{}"
输出: true
示例 3:

输入: "(]"
输出: false
示例 4:

输入: "([)]"
输出: false
示例 5:

输入: "{[]}"
输出: true

1.output_match_bracket.php

这是一个调用和打印输出结果的展示文件：

<?php
require 'MatchBracket.php';
$matchBracket = new MatchBracket();
$str = "[()[{[]}]{}]({([]([()][]))})";
var_dump($matchBracket->isValid($str)); //输出true
$str = "[()[{[]}]{}]({([]([()][}]))})";
var_dump($matchBracket->isValid($str)); //输出false

2.MatchBracket 类

这个类主要作用是接收需要匹配的字符串，然后调用 入栈 和 出栈 逻辑，通过巧妙的抵消花括号的方法来判断花括号是否封闭：

<?php
require 'StackStruct.php';
/**
 * 匹配花括号
 * Class MatchBracket
 */class MatchBracket
{
 /**
 * 判断花括号是否有效封闭
 * @param string $str
 * @return bool
 */ public function isValid(string $str): bool
 {
 $stackStruct = new StackStruct();
 //若字符串长度为奇数，则肯定不封闭
 if (strlen($str) % 2 == 1) {
 return false;
 }
 //先将花括号字符串依次入栈,若遇到 ] ) },需查看栈顶是否对应是 [ ( { for ($i = 0; $i < strlen($str); $i++) {
 if (!$stackStruct->isEmpty() && $str[$i] == "]" && $stackStruct->peek() != "[") {
 return false;
 } elseif (!$stackStruct->isEmpty() && $str[$i] == ")" && $stackStruct->peek() != "(") {
 return false;
 } elseif (!$stackStruct->isEmpty() && $str[$i] == "}" && $stackStruct->peek() != "{") {
 return false;
 } elseif (!$stackStruct->isEmpty() && $str[$i] == "]" && $stackStruct->peek() == "[") {
 $stackStruct->pop(); //出栈抵消
 } elseif (!$stackStruct->isEmpty() && $str[$i] == ")" && $stackStruct->peek() == "(") {
 $stackStruct->pop(); //出栈抵消
 } elseif (!$stackStruct->isEmpty() && $str[$i] == "}" && $stackStruct->peek() == "{") {
 $stackStruct->pop(); //出栈抵消
 } else {
 $stackStruct->push($str[$i]);
 }
 } //如 "$str=[({" ,最后栈不为空，则表示括号不封闭
 if (!$stackStruct->isEmpty()) {
 return false;
 }
 return true;
 }
}

3.StackStruct 栈类

这里是一个 栈 类，它的继承了数组类的方法，通过数组的增删查封装的一个 栈 类，实现了 入栈(push)、出栈(pop)、查看栈顶(peek) ：

<?php
require 'ArrayStruct.php';
require 'Stack.php';
/**
 * 数组实现栈
 * Class StackStruct
 */class StackStruct implements Stack
{
 //数组类对象，用于存放栈元素
 public $array = null;
 /**
 * 构造函数 定义栈的容量
 * ArrayStruct constructor.
 * @param int $capacity
 */
 public function __construct(int $capacity = 10)
 { $this->array = new ArrayStruct($capacity);
 }
 /**
 * 获取栈大小
 * @return int
 */ public function getSize(): int
 {
 return $this->array->getSize();
 }
 /**
 * 判断栈是否为空
 * @return bool
 */ public function isEmpty(): bool
 {
 return $this->array->isEmpty();
 }
 /**
 * 元素入栈
 */
 public function push($e): void
 {
 $this->array->addLast($e);
 }
 /**
 * 出栈
 * @return mixed
 */ public function pop()
 { return $this->array->removeLast();
 }
 /**
 * 查看栈顶元素
 * @return mixed
 */ public function peek()
 { return $this->array->getLast();
 }
 /**
 * 将栈数组转化为字符串
 * @return string
 */ public function toString(): string
 {
 return $this->array->toString();
 }
}

4.interface Stack

这里是 栈 类一个实现接口，里面定义了一些函数，这样 StackStrcut 继承它之后，必须重构里面的所有方法：

<?php
interface Stack
{
 /**
 * 获取栈大小
 * @return int
 */ public function getSize(): int;
 /**
 * 判断栈是否为空
 * @return bool
 */ public function isEmpty(): bool;
 /**
 * 元素入栈
 */
 public function push($e): void;
 /**
 * 出栈
 * @return mixed
 */ public function pop();
 /**
 * 查看栈顶元素
 * @return mixed
 */ public function peek();
}

5.ArrayStruct 数组类

这是封装好的一个数组类，能实现数组的基本功能：

<?php
/**
 * 数据结构-数组的实现
 * Class ArrayStruct
 */class ArrayStruct
{
 //用于存放数据
 protected $data = [];
 //用于标记数组大小
 protected $size = 0;
 //用于标记数组的容量
 protected $capacity = 10;
 /**
 * 构造函数 定义数组容量
 * ArrayStruct constructor.
 * @param int $capacity
 */
 public function __construct(int $capacity = 10)
 { $this->capacity = $capacity;
 }
 /**
 * 获取数组元素个数
 * @return int
 */ public function getSize(): int
 {
 return $this->size;
 }
 /**
 * 获取数组的容量
 * @return int
 */ public function getCapacity(): int
 {
 return $this->capacity;
 }
 /**
 * 判断数组是否为空
 * @return bool
 */ public function isEmpty(): bool
 {
 return $this->size == 0;
 }
 /**
 * 向数组指定位置插入元素
 * @param int $index
 * @param $e
 * @throws Exception
 */ public function add(int $index, $e): void
 {
 if ($this->size == $this->capacity) {
 $this->resize(2); //扩大到原来的2倍
 }
 if ($index < 0 || $index > $this->size) {
 echo "添加位置超出数组大小";
 exit; }
 //为了方便理解，[1,2,4,5,6],假设 $index = 3; $e = 100,插入之后[1,2,4,100,5,6]
 for ($i = $this->size; $i >= $index; $i--) {
 $this->data[$i] = $this->data[$i - 1];
 }
 $this->data[$index] = $e;
 $this->size++;
 }
 /**
 * 向数组末尾添加元素
 * @param $e
 * @throws Exception
 */ public function addLast($e): void
 {
 $this->add($this->size, $e);
 }
 /**
 * 向数组开头插入元素
 * @param $e
 * @throws Exception
 */ public function addFirst($e): void
 {
 $this->add(0, $e);
 }
 /**
 * 获取 index 位置数组元素
 * @param int $index
 * @return mixed
 */ public function get(int $index)
 { if ($index < 0 || $index > $this->size) {
 echo "index值超出元素的位置范围，";
 exit; }
 return $this->data[$index];
 }
 /**
 * 获取数组末尾元素
 * @return mixed
 */ public function getLast()
 { return $this->get($this->size - 1);
 }
 /**
 * 判断数组中是否存在某个元素
 * @param $e
 * @return bool
 */ public function contains($e): bool
 {
 for ($i = 1; $i < $this->size; $i++) {
 if ($this->data[$i] == $e) {
 return true;
 }
 }
 return false;
 }
 /**
 * 查某个元素在数组的位置索引值，若不存在则返回 -1
 * @param $e
 * @return int
 */ public function find($e): int
 {
 for ($i = 0; $i < $this->size; $i++) {
 if ($this->data[$i] == $e) {
 return $i;
 }
 }
 return -1;
 }
 /**
 * 删除数组指定位置元素，返回删除元素的值
 * @param $index
 * @return mixed
 */ public function remove($index)
 { if ($index < 0 || $index > $this->size) {
 echo "index值超出元素的位置范围，";
 exit; }
 $e = $this->data[$index];
 for ($i = $index; $i < $this->size - 1; $i++) {
 $this->data[$i] = $this->data[$i + 1];
 }
 $this->size--;
 $this->data[$this->size] = null; //loitering objects ! =memory
 /** 若当前数组大小，小于容量的一半，则重新分配一半的数组空间大小 **/
 if ($this->size <= $this->capacity / 4 && $this->capacity % 2 == 0) {
 $this->resize(0.5);
 }
 return $e;
 }
 /**
 * 删除数组首个元素，返回删除元素的值
 */
 public function removeFirst()
 { return $this->remove(0);
 }
 /**
 * 删除数组首个元素，返回删除元素的值
 */
 public function removeLast()
 { return $this->remove($this->size - 1);
 }
 /**
 * 删除数组中特定元素
 * @param $e
 */
 public function removeElement($e)
 { for ($i = 0; $i < $this->size; $i++) {
 if ($this->data[$i] == $e) {
 $this->remove($i);
 $this->removeElement($e);
 break; }
 } }
 /**
 * 数组扩容，若是其他语言，如JAVA这里需要重新开辟空间
 * @param $factor
 */
 protected function resize($factor)
 { $this->capacity = $factor * $this->capacity;
 }
 /**
 * 将数组转化为字符串
 * @return string
 */ public function toString(): string
 {
 $str = "[";
 for ($i = 0; $i < $this->size; $i++) {
 $value_str = is_numeric($this->data[$i]) ? $this->data[$i] : "'{$this->data[$i]}'";
 $str .= $i . " => " . $value_str . ",";
 }
 $str = trim($str, ",");
 $str .= "]";
 return $str;
 }
}

Tips：若对 栈 不熟悉，可以参考之前文章数据结构-PHP通过 Array 类对象实现 "栈" 和数据结构-PHP实现Array

特别申明：本文内容来源网络，版权归原作者所有，如有侵权请立即与我们联系（cy198701067573@163.com），我们将及时处理。