查找表达式是否具有重复的括号


难度级别 易得奖学金
经常问 亚马逊 事实集 神谕

给定一个 绳子 包含圆括号。 查找表达式/字符串是否包含重复的括号。

括号重复

当一个表达式位于相同类型的平衡括号的中间或周围时,即不止一次地在相同类型的左括号和右括号之间包含一个重复的括号。 例如–((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),因为我们使用堆栈空间来存储字符。

參考資料