How to validate brackets in equation string in PHP

Question

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:(

Do you allow nested brackets? e.g. `((1 + 3) / (2 - 5)) + 5`... if so, probably best to use a proper lexer — Mark Baker, Mar 31 '13 at 10:38
I think your checking condition isn't right. It should be `if ($counter1 != 0 || $counter2 != 0){ return false; }`. You start with both counters `0` and they both should be `0` when you finished validating if the brackets are valid. That is in addition to the comment of @MarkBaker :-) — Havelock, Mar 31 '13 at 10:38
ircmaxell's answer to http://stackoverflow.com/questions/12692727/how-to-make-a-calculator-in-php is a good starting point for a mathematical formula lexer (and a parser if you need that as well) — Mark Baker, Mar 31 '13 at 10:43

Shoe · Accepted Answer · 2013-03-31T11:13:10.647

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;

+1 smart and minimalistic. Also a stack machine is exactly what is used to check whether strings belong to the language, defined by a context-free grammar. — Havelock, Mar 31 '13 at 11:08
good approach. I would have pushed the `( / [` itself to the stack and checked for `) / ]` while popping. — Ejaz, Mar 31 '13 at 11:23

Havelock · Answer 2 · 2013-03-31T11:02:46.143

1

The usual way of validating such syntactic rules is using a Context-free grammar - see the examples and you'll find exactly what you're trying to do as an example :-) And you can apply the rules of such a grammar by using a lexer as Mark Baker pointed out.
In you code you're only making sure that the number of opening brackets matches the number of closing brackets and that is the flaw. Also as I've pointed out in my comment your last condition should be

if ($counter1 != 0 || $counter2 != 0){
    return false;
}

In your current case true will be returned when any of the counters is >=0. Try out with a simple case hasMatchedParenthesis('[5] * 3 - ( 4 - 7 * [3-6');, which will return true even though it's wrong.

edited Mar 31 '13 at 11:02

answered Mar 31 '13 at 10:48

Havelock

6,913
4
34
42

Hello, do you have some link to see how can I apply this **Context-free-grammar** in php? to make the same validation of this question – Emilio Gort Sep 24 '14 at 16:13
1

@EmilioGort you can [find some resources](https://www.google.com/search?q=php%20context%20free%20grammar%20parser) on the net – Havelock Sep 26 '14 at 06:35

score 1 · Answer 3 · answered Jun 20 '17 at 05:38

I've written following realisation.

function check_brackets_balance($string, $bracket_map = false) {
    $bracket_map = $bracket_map ?: [ '[' => ']', '{' => '}', '(' => ')' ];
    $bracket_map_flipped = array_flip($bracket_map);
    $length = mb_strlen($string);
    $brackets_stack = [];
    for ($i = 0; $i < $length; $i++) {
        $current_char = $string[$i];
        if (isset($bracket_map[$current_char])) {
            $brackets_stack[] = $bracket_map[$current_char];
        } else if (isset($bracket_map_flipped[$current_char])) {
            $expected = array_pop($brackets_stack);
            if (($expected === NULL) || ($current_char != $expected)) {
                return false;
            }
        }
    }
    return empty($brackets_stack);
}

It also uses stack, but takes less code and has additional parameter for your own brackets set.

check_brackets_balance('[5] * 3 - ( 4 - 7 * [3-6])'); // true
check_brackets_balance('( 5 * 3 [ 6 ) - 6]')); // false

How to validate brackets in equation string in PHP

3 Answers3