Menu
I was wandering if someone good in PHP could advise on how to validate brackets in an expression sting like this:
( 5 * 3 [ 6 ) - 6]
which is wrong expression. I need a function to to do this. Here is what I have tried so far:
<?php
function hasMatchedParenthesis($string) {
$counter1 = 0;
$counter2 = 0;
$length = strlen($string);
for ($i = 0;$i < $length; $i++) {
$char = $string[$i];
if( $char == '(' ) {
$counter1 ++;
} elseif( $char == ')' ) {
$counter1 --;
}
for($j =0;$j < $length; $j++) {
$char = $string[$j];
if( $char == '[' ) {
$counter2 ++;
} elseif( $char == ']' ) {
$counter2 --;
}
}
if( $counter1 < 0 || $counter2 < 0) {
return false;
}
}
echo 'ok';;
}
hasMatchedParenthesis('[5] * 3 - ( 4 - 7 * [3-6])'); // this is ok!
hasMatchedParenthesis('( 5 * 3 [ 6 ) - 6]'); // this returns as TRUE, but it is not!
?>
Pleas help me to resolve validation of '[ 6 )' thing! I dont know how to do it:(
748
An input string is valid if: Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order. Every close bracket has a corresponding open bracket of the same type.
The valid parentheses problem involves checking that: all the parentheses are matched, i.e., every opening parenthesis has a corresponding closing parenthesis. the matched parentheses are in the correct order, i.e., an opening parenthesis should come before the closing parenthesis.
Check for Balanced Bracket expression using Stack:Whenever you hit a closing bracket, search if the top of the stack is the opening bracket of the same nature. If this holds then pop the stack and continue the iteration, in the end if the stack is empty, it means all brackets are well-formed .
One approach to check balanced parentheses is to use stack. Each time, when an open parentheses is encountered push it in the stack, and when closed parenthesis is encountered, match it with the top of stack and pop it. If stack is empty at the end, return Balanced otherwise, Unbalanced.
The first idea that comes to my mind is to use a stack. PHP provides two functions to treat an array as a stack: array_push and array_pop. We can use them to create a stack of 0 (we are inside an opening () and 1 (we are inside a [) and check whenever a closing bracket matches with the last value we inserted:
function hasMatchedParenthesis($string) {
$len = strlen($string);
$stack = array;
for ($i = 0; $i < $len; $i++) {
switch ($string[$i]) {
case '(': array_push($stack, 0); break;
case ')':
if (array_pop($stack) !== 0)
return false;
break;
case '[': array_push($stack, 1); break;
case ']':
if (array_pop($stack) !== 1)
return false;
break;
default: break;
}
}
return (empty($stack));
}
Notice that you can extend this to any other pair of characters including { and }:
case '{': array_push($stack, 2); break;
case '}':
if (array_pop($stack) !== 2)
return false;
break;
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
