Уравнотежен израз са заменом


Ниво тешкоће Средњи
Често питани у амазонка Пешачење пророчанство Снапцхат Снапдеал Валмарт Лабс випро Иатра Зохо
Стацк низ

У проблему уравнотеженог израза са заменом дали смо низ с који садржи заграде, тј. '(', ')', '[', ']', '{', '}'. Тхе низ такође садржи к на неким местима као замену заграде. Проверите да ли низ може да се претвори у израз са важећом заградом након замене свих к с било којом заградом.

Уравнотежен израз са заменом

Пример

Улазни 

с = “{(к [к])}”

Излаз

 да

Улазни

с = “[{к} (к)]”

Излаз 

Не

Алгоритам

Сада знамо ставку проблема уравнотеженог израза са заменом. Дакле, дошли смо до доњег алгоритма за решење.

  1. Иницијализујте низ с, низ типова знакова и променљиву да бисте тренутни индекс сачували као 0.
  2. Ако је дужина низа једнака тренутном индексу, вратите 1 ако је стек празан елсе 0.
  3. Проверите да ли је знак у тренутном индексу у низу почетна заграда, гурните га у стог и вратите рекурзивни позив са тренутним индексом као тренутни индекс + 1.
  4. Иначе ако је знак у тренутном индексу у низу завршна заграда, проверите да ли је стек празан ретурн 0 елсе проверите да ли врх стека није једнак отварању заграде тренутном знаку у низу, вратите 0. Поп врх и узвратите рекурзивни позив са тренутним индексом као тренутним индексом + 1.
  5. Иначе ако је знак у тренутном индексу у низу једнак к, створите привремени стек једнак старом и гурните знак у њега.
  6. Направите променљиву рес. Упути рекурзивни позив са тренутним индексом као тренутним индексом + 1 и привременим стеком. Похраните његов резултат у рес.
  7. Ако је рес једнак 1, вратите 1.
  8. Ако је стари стек празан, вратите 0.
  9. Скочите врх из старог стека и вратите рекурзивни позив са тренутним индексом као тренутним индексом + 1 и старим стеком.

Ц ++ програм за уравнотежен израз са заменом

#include <bits/stdc++.h> 
using namespace std; 
  
int isMatching(char a, char b){ 
    if((a == '{' && b == '}') || (a == '[' && b == ']') || (a == '(' && b == ')') || a == 'x') 
      return 1; 
    return 0; 
} 
  
int isBalanced(string s, stack<char> ele, int ind){ 
  
    if(ind == s.length()){  
        return ele.empty();
    }
  
    char topEle; 
  
    int res; 
  
    if((s[ind] == '{') || (s[ind] == '(') || (s[ind] == '[')){ 
        ele.push(s[ind]); 
        return isBalanced(s, ele, ind + 1); 
    } 
  
    else if((s[ind] == '}') || (s[ind] == ')') || (s[ind] == ']')){ 
  
        if(ele.empty()){  
            return 0; 
        }
  
        topEle = ele.top(); 
        ele.pop(); 
  
        if(!isMatching(topEle, s[ind])){  
            return 0; 
        }
          
        return isBalanced(s, ele, ind + 1); 
    } 
  
    else if(s[ind] == 'x'){ 
        stack<char> tmp = ele; 
        tmp.push(s[ind]); 
        res = isBalanced(s, tmp, ind + 1); 
        if(res){ 
            return 1;
        }
        if(ele.empty()){ 
            return 0; 
        }
        ele.pop();
        
        return isBalanced(s, ele, ind + 1); 
    } 
} 
  
int main(){ 
    string s = "{(x[x])}"; 
    stack<char> ele;
    
    if(isBalanced(s, ele, 0)){  
        cout<<"Yes";   
    }
    
    else{ 
        cout<<"No";
    }
    return 0; 
}
Yes

Јава програм за уравнотежен израз са заменом

import java.util.Stack; 
  
class BalancedExpression{ 
    
    static int isMatching(char a, char b){ 
        if((a == '{' && b == '}') || (a == '[' && b == ']') || (a == '(' && b == ')') || a == 'x'){ 
            return 1; 
        } 
        return 0; 
    } 
  
    static int isBalanced(String s, Stack<Character> ele, int ind){ 
  
        if(ind == s.length()){ 
            if(ele.size() == 0){ 
                return 1; 
            } 
            else{ 
                return 0; 
            } 
        } 
  
        char topEle; 
  
        int res; 
  
        if((s.charAt(ind) == '{') || (s.charAt(ind) == '(') || (s.charAt(ind) == '[')){ 
            ele.push(s.charAt(ind)); 
            return isBalanced(s, ele, ind + 1); 
        } 
        
        else if((s.charAt(ind) == '}') || (s.charAt(ind) == ')') || (s.charAt(ind) == ']')){ 
  
            if(ele.size() == 0){ 
                return 0; 
            } 
  
            topEle = ele.peek(); 
            ele.pop(); 
  
            if(isMatching(topEle, s.charAt(ind)) == 0){ 
                return 0; 
            } 
  
            return isBalanced(s, ele, ind + 1); 
        } 
        
        else if(s.charAt(ind) == 'x'){ 
            Stack<Character> tmp = new Stack<>(); 
            
            tmp.addAll(ele);  
            tmp.push(s.charAt(ind)); 
            res = isBalanced(s, tmp, ind + 1); 
            
            if(res == 1){ 
                return 1; 
            } 
            
            if(ele.size() == 0){ 
                return 0; 
            } 
            
            ele.pop(); 
            return isBalanced(s, ele, ind + 1); 
        } 
        return 1; 
    } 
  
    public static void main(String[] args) { 
  
        String s = "{(x[x])}"; 
        Stack<Character> ele = new Stack<Character>(); 
  
        if(isBalanced(s, ele, 0) != 0){ 
            System.out.println("Yes"); 
        } 
        
        else{ 
            System.out.println("No"); 
        } 
    } 
}
Yes

Анализа сложености

Сложеност времена: О ((2 ^ н) * н) где је н дужина низа.

Помоћни простор: О (н) јер смо користили н додатног простора у стеку.

Референце