识别并标记表达式中不匹配的括号


难度级别 中等
经常问 TCS

在识别和标记表达式问题中不匹配的括号时,我们给出了一个 绳子 长度为n的s,其中包含一个表达式。 找到平衡括号对,并将所有平衡开括号替换为0,将平衡闭括号替换为1,将非平衡括号替换为-1。

使用案列

让给定的字符串s =“((((abc))((d)))))”,在此我们使用给定的字符串标识并标记表达式中不匹配的括号。

在此,第一个括号与最后一个第三括号保持平衡。 因此,分别用0和1代替开括号和闭括号。

  • 此后,第二个括号与子表达式“ abc”的第二个结束括号保持平衡,因此,请分别用0和1替换开头和结尾括号。
  • 类似地,第三个括号与子表达式“ abc”的第一个闭合括号相抵,因此,分别用0和1代替开头和结尾括号。
  • 第四个开始括号与子表达式“ d”的第二个结束括号保持平衡,因此,分别用0和1替换开始和结束括号。
  • 类似地,第五个左括号与子表达式“ d”的第一个右括号保持平衡,因此,分别用0和1替换开和右括号。
  • 最后,将所有不平衡括号替换为-1。
  • 因此结果= 000abc1100d111-1-1

识别并标记表达式中不匹配的括号

输入: s =“(((a)”

输出: -10a1

输入: s =“(a))”

输出: 0a1-1

识别和标记表达式中不匹配括号的算法

  1. 初始化包含表达式的长度为n的字符串s。
  2. 创建一个 数据结构。
  3. 遍历给定的字符串,并检查字符串中当前索引处的字符是否等于左括号,然后将当前索引压入/插入堆栈中。
  4. 否则,检查字符串中当前索引处的字符是否等于右括号,检查堆栈是否为空,替换或更新字符串中当前索引处的字符为-1。 否则,将所有左括号都用0替换,将右括号都用1替换。
  5. 当堆栈不为空时,将堆栈中的所有字符更新为-1。
  6. 打印更新的字符串。

识别和标记表达式中不匹配括号的C ++程序

#include <bits/stdc++.h> 
using namespace std; 
  
void identifyParenthesis(string s){
    stack<int> st; 
  
    for(int i = 0; i < s.length(); i++){ 
        if(s[i] == '('){  
            st.push(i); 
        }
          
        else if(s[i] == ')'){ 
  
            if(st.empty()){  
                s.replace(i, 1, "-1"); 
            }
              
            else{ 
                s.replace(i, 1, "1"); 
                s.replace(st.top(), 1, "0"); 
                st.pop(); 
            } 
        } 
    } 
  
    while(!st.empty()){ 
        s.replace(st.top(), 1, "-1"); 
        st.pop(); 
    } 
  
    cout << s << endl; 
} 
  
int main(){ 
    string s = "(a))"; 
    
    identifyParenthesis(s); 
    
    return 0; 
}
0a1-1

识别和标记表达式中不匹配括号的Java程序

import java.util.*; 
  
class MarkParenthesis{ 
    
    static void identifyParenthesis(StringBuffer s){  
        Stack<Integer> st = new Stack<Integer>();  
      
        for(int i = 0; i < s.length(); i++){  
            if (s.charAt(i) == '('){  
                st.push(i);  
            }
              
            else if(s.charAt(i) == ')'){  
                if(st.empty()){  
                    s.replace(i, i + 1, "-1");  
                }
                  
                else{  
                    s.replace(i, i + 1, "1");  
                    s.replace(st.peek(), st.peek() + 1, "0");  
                    st.pop();  
                }  
            }  
        }  
      
        while(!st.empty()){  
            s.replace(st.peek(), 1, "-1");  
            st.pop();  
        }  
      
        System.out.println(s); 
    }  
      
    public static void main(String[] args){
        
        StringBuffer s = new StringBuffer("(a))");  
        identifyParenthesis(s);  
        
    } 
}
0a1-1

复杂度分析

时间复杂度: O(n)其中n是给定表达式中的字符数。

空间复杂度: O(n),因为我们使用空间来存储n个元素。

參考資料