数据结构实现括号匹配
时间: 2023-11-26 16:46:49 浏览: 39
以下是基于PHP实现栈数据结构和括号匹配算法的例子:
```php
class Stack {
private $stackArray = array();
private $top = -1;
public function push($element) {
$this->top++;
$this->stackArray[$this->top] = $element;
}
public function pop() {
if ($this->top == -1) {
return null;
}
$element = $this->stackArray[$this->top];
unset($this->stackArray[$this->top]);
$this->top--;
return $element;
}
public function isEmpty() {
return ($this->top == -1);
}
public function peek() {
if ($this->top == -1) {
return null;
}
return $this->stackArray[$this->top];
}
}
function isBalanced($expression) {
$stack = new Stack();
for ($i = 0; $i < strlen($expression); $i++) {
$char = $expression[$i];
if ($char == '(' || $char == '[' || $char == '{') {
$stack->push($char);
} else if ($char == ')' || $char == ']' || $char == '}') {
if ($stack->isEmpty()) {
return false;
}
$topChar = $stack->pop();
if (($char == ')' && $topChar != '(') || ($char == ']' && $topChar != '[') || ($char == '}' && $topChar != '{')) {
return false;
}
}
}
return $stack->isEmpty();
}
// 示例
$expression1 = "([]{})";
$expression2 = "[()[]{}]";
$expression3 = "([)]";
if (isBalanced($expression1)) {
echo $expression1 . " is balanced\n";
} else {
echo $expression1 . " is not balanced\n";
}
if (isBalanced($expression2)) {
echo $expression2 . " is balanced\n";
} else {
echo $expression2 . " is not balanced\n";}
if (isBalanced($expression3)) {
echo $expression3 . " is balanced\n";
} else {
echo $expression3 . " is not balanced\n";
}
```