()*  -> In-valid
()(* -> valid
*)() -> valid
()** -> valid
)(   -> In-valid
)*   -> In-valid

I tried and stuck to implement the code, as I know that we have to do with Stack, but I just stuck there, can someone PHP expert one did it and :) and explain it.

• Input would be the string like "()*".
• "*" can used as open,close parenthesis
• open(left) parenthesis should have close (right) parenthesis in a valid expression.

I tried to do it with following code don't know my direction was right or not :)

$scenario = "()*";
$stackOne = str_split($scenario);
$stackTwo = array();
$counter = 1;
function push(array $arr, ?string $value)
{
    $arr[] = $value;
    return $arr;
}

function pop(array $arr)
{
    $count = count($arr) -1;
    if ($count > 0) unset($arr[$count]);
    return $arr;
}

function isValid(array $arr,string $value)
{
    $mapping= [
        "*" => ["(", ")", "*"],
        "(" => ["*", ")"],
        ")" => ["*", "("],
    ];
    if (empty($arr)) return "push";
    dd($arr[count($arr) - 1]);
    if(in_array($arr[count($arr) - 1] ,$mapping[$value])) return "pop";
}

foreach ($stackOne as $key => $value) {
    $output = isValid($stackTwo, $value);
    if ($output === "push") {
        $stackTwo = push($stackTwo, $value);
    } elseif ($output === "pop") {
        $stackTwo = pop($stackTwo);
    }
}

print_r($stackTwo);

CodePudding user response：

You can check for balance validity with 4 conditions:

• If there is a ), we should have at least 1 ( or * in our account so far, both would work.

• If there are enough * for ( to be paired with ).

• If there are still any * left, we can either use them as ( and ) pair or use them as empty spaces. Here, whether the leftover count is even or odd won't matter since we can substitute them as empty space.

• There could be leftover open braces at the end. For this to be balanced, we need to have * after them to pair them with ). So, we do another run in the end to check for it's validity.

Snippet:

<?php

function isValid($str){
    $star = 0;
    $open = [];
    $len = strlen($str);
    
    for($i = 0; $i < $len;   $i){
        if($str[ $i ] == ')'){
            if(count($open) > 0) array_pop($open);
            elseif($star > 0) $star--;
            else return false;
        }elseif( $str[ $i ] == '('){
            array_push($open, $i);
        }else{
            $star  ;
        }
    }
    
    if(count($open) === 0) return true;
    // check leftover open braces from the back
    $star = $ptr = 0;
    $open = array_reverse($open);
    
    for($i = $len - 1; $i >= 0 && $ptr < count($open); --$i){
        if($str[ $i ] == '*'){
            $star  ;
        }else if($i == $open[ $ptr ]){
            if($star == 0) return false;
            $star--;
            $ptr  ;
        }
    }
    
    return true;
}

Online Demo