查找表達式是否具有重複的括號


難度級別 容易獎學金
經常問 亞馬遜 事實集 神諭

給定一個 包含圓括號。 查找表達式/字符串是否包含重複的括號。

括號重複

當一個表達式位於相同類型的平衡括號的中間或周圍時,即多次被包圍在相同類型的左括號和右括號之間,則表示該表達式具有重複的括號。 例如–((a + b)),即整個表達式位於兩個相似括號的中間,但在表達式(a +(b))中,整個表達式或任何子表達式都不包含重複的括號。

例如 -

查找表達式是否具有重複的括號

輸入: s =“((((a +(b))+(c + d)))”

輸出: 表達式包含重複的括號。

輸入: s =“(((a + b)+ c + d)”

輸出: 表達式不包含重複的括號。

使用堆棧的方法

創建一個堆棧。 遍歷或迭代給定的字符串。 檢查每個字符,如果它等於'('或任何運算符或操作數,則將其壓入堆棧。如果它等於')',則彈出字符,直到找到相同種類的開放括號。 使用一個count變量,對每個字符遞增,直到找到開頭的括號'('。如果變量count小於1,則返回true,否則找不到重複的括號。

算法

  1. 初始化包含平衡括號的字符串表達式。
  2. 初始化一個 存儲字符。
  3. 遍歷字符串並檢查當前字符是否不是右括號,然後將字符壓入堆棧。
  4. 否則彈出堆棧的頂部並初始化一個計數器,以將括號內的元素計數為0。當頂部不等於圓括號時,遞增計數器並彈出頂部。
  5. 檢查其中的元素是否小於1,返回1。
  6. 返回false。

用於表達式的C ++程序是否具有重複的括號

#include <bits/stdc++.h> 
using namespace std; 
  
bool isDuplicate(string s){ 
    
    stack<char> Stack; 
  
    for(char ch : s){ 
        
        if(ch == ')'){ 
            
            char top = Stack.top(); 
            Stack.pop(); 
  
            int elementsInside = 0; 
            
            while(top != '('){ 
                elementsInside++; 
                top = Stack.top(); 
                Stack.pop(); 
            } 
            
            if(elementsInside < 1){ 
                return 1; 
            } 
        } 
  
        else{
            Stack.push(ch); 
        }    
    } 
  
    return false; 
} 
  
  
int main(){ 
    
    string s = "(((a+(b))+(c+d)))"; 
  
    if(isDuplicate(s)){ 
        cout<<"Expression contains duplicate parenthesis.";
    }    
    else{
        cout<<"Expression does not contain duplicate parenthesis."; 
    }    
  
    return 0; 
}
Expression contains duplicate parenthesis.

用於表達式的Java程序是否具有重複的括號

import java.util.Stack; 
  
class Parenthesis{ 
  
    static boolean isDuplicate(String s){ 
        
        Stack<Character> Stack = new Stack<>(); 
  
        char[] str = s.toCharArray(); 
        for(char ch : str) { 
            
            if (ch == ')') { 
                
                char top = Stack.peek(); 
                Stack.pop(); 
  
                int elementsInside = 0; 
                
                while (top != '(') { 
                    elementsInside++; 
                    top = Stack.peek(); 
                    Stack.pop(); 
                } 
                
                if (elementsInside < 1){ 
                    return true; 
                } 
            } 
            
            else{ 
                Stack.push(ch); 
            } 
        } 
  
        return false; 
    } 
  
    public static void main(String[] args) { 
  
        String s = "(((a+(b))+(c+d)))"; 
  
        if(isDuplicate(s)){ 
            System.out.println("Expression contains duplicate parenthesis."); 
        } 
        
        else{ 
            System.out.println("Expression does not contain duplicate parenthesis."); 
        } 
  
    } 
}
Expression contains duplicate parenthesis.

表達的複雜性分析是否有重複的括號

時間複雜度: O(n)其中n是表達式中的字符數。

輔助空間: O(n),因為我們使用堆棧空間來存儲字符。

參考