反向括号 - Codefights

Question

我很难用 JavaScript

解决这个问题

给你一个由英文字母、标点符号、空白字符和括号组成的字符串s。保证s中的括号组成正则括号序列

你的任务是反转每对匹配括号中的字符串，从最里面的那个开始。

示例

对于字符串 s = a(bc)de 输出应该是

reverseParentheses(s) = "acbde".

Input/Output

[time limit] 4000ms (js)
[input] string s

由英文字母、标点符号、空白字符和括号组成的字符串。保证括号组成正则括号序列

限制条件：

5 ≤ x.length ≤ 55.

[输出] 字符串

它必须使用以下输入：

s: a(bcdefghijkl(mno)p)q 预期输出： apmnolkjihgfedcbq
s: co(de(fight)s) 预期输出： cosfighted

Answer 1

function reverseParentheses(s) {
    if (s.includes('(')){
        return reverseParentheses(reverseOnce(s));
    } else {     
        return s;
    }
}

function reverseOnce(s){
    var regexp = /\(([^()]*)\)/i;
    var subStr = regexp.exec(s)[1];
    subStr = subStr.split('').reverse().join('');
    return s.replace(regexp, subStr)
}

Answer 2

def reverseParentheses(s):
    for i in range(len(s)):
        if s[i] == "(":
            start = i
            print (s[:start])
        if s[i] == ")":
            end = i
            print (end)
            return reverseParentheses(s[:start] + s[start+1:end][::-1] + s[end+1:])
    return s

Answer 3

解决方法如下：

const reverse = (str) => str.split('').reverse().join('');

const reverseParentheses = (s) => {
    while (s.includes('(')) {
        var l = s.lastIndexOf('(');
        var r = s.indexOf(')', s.lastIndexOf('('));
        s = s.slice(0, l) + reverse(s.slice(l + 1, r)) + (r + 1 === s.length ? s.slice(r, -1) : s.slice(r + 1));
    }
    return s;
};

Answer 4

public static String reverseParentheses(String s) {
    StringBuilder sb = new StringBuilder();
    char[] sArray = s.toCharArray();
    int[] firstIndex = new int[s.length()]; //所有'('的索引
    int[] lastIndex = new int[s.length()]; //所有')'的索引
    int num = 0; // 表示遇到')'括号的次数
    int count = 0; // 表示遇到"("括号的次数
    boolean flag = false; //多种情况的判断
    int index; //')'对应'('的位置
    int countParentheses; //')'对应的'('的前面的括号个数
    for (int i = 0; i < sArray.length; i++) {
        if (sArray[i] == '(') {
            //第一种情况
            if (count == num && count != 0) {
                flag = true;
            } else if (count - num > 1 && num != 0) {//第三种情况
                flag = true;
            }
            firstIndex[count] = i;
            count++;
            continue;

        } else if (sArray[i] == ')') {
            System.out.println("开始->遇到')'：" + sb);
            lastIndex[num] = i;
            if (flag) {
                index = count - num;
                countParentheses = count + num;
                flag = false;
            } else {
                //第二种情况
                index = count - num - 1;
                countParentheses = count - num;

            }
            System.out.println("截取初始位置:" + (firstIndex[index] - (countParentheses) + 1));
            String s1 = sb.substring(firstIndex[index] - (countParentheses) + 1, lastIndex[num] - num - count);
            System.out.println("截取出括号内的字符串：" + s1);
            StringBuilder getString = new StringBuilder();
            getString.append(s1);
            getString.reverse();//反转
            System.out.println("替代起始位置：" + (firstIndex[index] - (countParentheses) + 1));
            System.out.println("替代的末位置:" + (lastIndex[num] - count - num));
            System.out.println("字符串长度：" + getString.toString().length());
            sb.replace(firstIndex[index] - (countParentheses) + 1, lastIndex[num] - count - num,
                    getString.toString().trim());
            System.out.println("反转后：" + sb);
            num++;
            continue;

        } else if (sArray[i] == ')' && count == num) {

        } else {
            sb.append(sArray[i]);
        }
    }

    System.out.println("...." + sb);
    return sb.toString();
}

Answer 5

给定一个大小为 n 的字符串，这是一个用 C 编写的递归代码，其运行时间复杂度为 O(n)。代码背后的想法是从字符串的开头开始，每次遇到左括号时，切换到右括号并向后打印，然后在右括号后完成打印。请注意，当您向后打印时，左括号“[”被视为右括号，反之亦然用于右括号“]”。最大字符串大小为 100 万，如果需要处理更长的字符串，请更改数组大小。

#include <stdio.h>
#include <string.h>
int n, other[1000010], stt[1000010];
char st[1000010];

void rec(int i, int dir) {
    if(i >= n) return;
    if(st[i] == '[') {
        if(dir == 1) { // going right with '[' means opening
            rec(other[i]-1, -dir); // go to the closing bracket and change direction
            rec(other[i]+1, dir); // continue after the closing bracket after finishing
        }
        return;
    }

    if(st[i] == ']') {
        if(dir == -1) { // going left with ']' means opening
            rec(other[i]+1, -dir); // go to the closing bracket and change direction
            rec(other[i]-1, dir); // continue after the closing bracket after finishing
        }
        return;
    }
    putchar(st[i]); // print character
    rec(i+dir, dir); // continue same direction
}

int main() {
    scanf("%s", st);
    n = strlen(st);
    for(int i=0, j, k=0; i<n; ++i) {
        if(st[i] == '[') stt[k++] = i;
        else if(st[i] == ']')  {
            j = stt[--k];
            other[i] = j, other[j] = i;
        }
    }
    rec(0, 1); // start from 0, with direction 1 (right)
    return 0;
}

Answer 6

这是我没有使用正则表达式的JS解决方案，对于初学者来说可能更容易理解。注释使代码 self-explanatory 但想法是找到最后一个左括号（如果表达式有嵌套括号），然后找到匹配的右括号，反转里面的文本并保留运行函数直到字符串不再有左括号（根据问题的定义，不再有右括号）。

function reverseParentheses(s) {
    // We keep running the function while 
    // there's an opening bracket in the string
    while (s.indexOf("(") !== -1) {
        s = reverseP(s);
    }
    return s;
}

function reverseP(s) {
    let len = s.length;
    // We find the innermost/last opening bracket,
    // and then we're going to find the matching closing bracket,
    // which is the next closing bracket after the opening bracket
    let openBracketInd = s.lastIndexOf("(");
    
    // The characters before the opening bracket
    let beforeBracket = s.slice(0, openBracketInd+1);
    
    // The characters before the opening bracket
    let afterBracket = s.slice(openBracketInd+1, len);
    
    // To get the index of the closing bracket we add the 
    // characters before the bracket to the index of the first closing
    // bracket in the string after the opening bracket
    let closeBracketInd = beforeBracket.length + afterBracket.indexOf(")");
    
    // Once we have the indexes, we're going to slice the string 
    // to remove the brackets
    let firstPart = s.slice(0, openBracketInd);
    let secondPart = s.slice(closeBracketInd+1, len);
    let middle = s.slice(openBracketInd+1, closeBracketInd);
    
    // We reverse the string between the brackets
    middle = middle.split('').reverse().join('');
    
    // And finally we join the parts and return the string
    return firstPart+middle+secondPart;
}

Answer 7

这是一个使用正则表达式的递归解决方案，当正则表达式中有匹配项时调用 reverseString 方法，该匹配项使用替换函数来替换反向字符串。一旦被逆转，它就会再次循环，直到没有更多的匹配项..

function reverseParentheses(s) {
    const reverseString = str => (str === '') ? '' : reverseString(str.substr(1)) + str.charAt(0);
    const regex = /(\([\w\s\[\]!\.\,\;\:\?]*\))/g;
    const iterator = a => {
        if(regex.test(a)){
            a=a.replace(regex, full => reverseString(full.replace(/[()]/g,'')));    
            return iterator(a);
        } else  return a;
    }
    return iterator(s);   
}

Answer 8

对于Python 3（不确定Python 2），此代码有效。这确实假设（如 Code Fights 上的问题所述）每个括号都是一对括号的一部分。

def reverseParentheses(s):
    from collections import Counter
    for i in range(Counter(s)['(']):
        one = s.rsplit('(',1)
        two = one[1].split(')',1)
        s = one[0]+two[0].replace(two[0],two[0][::-1]+two[1])
        print(s)
    return s

Answer 9

def reverseParentheses(s)
  0 while s.gsub!(/\(([^()]*)\)/) { .reverse }
  return s
end

Answer 10

F# 中的解决方案：

let foldi fold first source =
    source
    |> List.fold (fun (prev,i) c -> (fold i prev c,i + 1)) (first,0)
    |> fst

let reverseParentheses (s: string) =
    let go pos (stack: list<list<char>>) (c: char) : list<list<char>> =
        let fail () = failwithf "Parse error at pos %d, char '%c'." pos c
        match c with
        | '(' -> [] :: stack
        | ')' ->
            match stack with
            | top :: next :: rest -> ((List.rev top @ next) :: rest)
            | _ -> fail ()
        | _ ->
            match stack with
            | top :: rest -> ((c :: top) :: rest)
            | _ -> fail ()
    s |> Seq.toList |> foldi go [[]] |> List.head |> List.rev |> List.toArray |> String

Answer 11

在 JS 中

使用正则表达式

function reverseInParentheses(s) {
    if (s.match(/\([a-z]*\)/)) {
        return reverseInParentheses(s.replace(/\([a-z]*\)/, 
            Array.from(s.match(/\([a-z]*\)/)[0].replace(/\(|\)/g,'')).reverse().join('')));
    }
    else return s;
}

简单方法：-

function reverseInParentheses(s) {
    while (true) {
        let c = s.indexOf(")");    
        if (c === -1) break;
        let o = s.substring(0, c).lastIndexOf("(");
        let start = s.substring(0, o);
        let middle = s.substring(o + 1, c).split("").reverse().join("");
        let end = s.substring(c + 1, s.length);
        s = start + middle + end;
    }
    return s;
}

在Python中：

简单方法

def reverseInParentheses(s):
    return eval('"' + s.replace('(', '"+("').replace(')', '")[::-1]+"') + '"')

使用堆栈方法

def reverseInParentheses(s):
    stack = []
    for x in s:
        if x == ")":
            tmp = ""
            while stack[-1] != "(":
                tmp += stack.pop()
            stack.pop() # pop the (
            for item in tmp:
                stack.append(item)
        else:
            stack.append(x)

    return "".join(stack)

在 C++ 中

简单方法：-

reverseString 函数将使用交换方法反转字符串，而 reverseParentheses 函数将递归更新字符串。

string reverseString(string s){
    for(int i = 0;i < s.length()/2;i++){
        char t = s[s.length()-1-i];
        s[s.length()-1-i] = s[i];
        s[i] = t;
    }
    return s;
}
string reverseInParentheses(string s) {
    int beg = 0;
    int end = s.length() - 1;
    for(int i = 0; i < s.length(); i++){
        if(s[i] == '(')
            beg = i;
        if(s[i] == ')'){
            end = i;
            string temp = s.substr(beg + 1, end - beg - 1);
            return reverseInParentheses(s.substr(0, beg) + reverseString(temp) + s.substr(end + 1));
         }
    }
    return s;
}

Answer 12

在Java中： 简单方法

String reverseInParentheses(String inputString) {

    StringBuilder str = new StringBuilder();
    int start = 0;
    int end = inputString.length() - 1;
    str.setLength(0);
    if (inputString.contains("(")) {
        start = inputString.lastIndexOf("(");
        end = inputString.indexOf(")", start);
        str.append(inputString, start+1, end);
        return reverseInParentheses(inputString.substring(0, start) + str.reverse().toString() + inputString.substring(end+1));
    }
    return inputString;
}

Answer 13

在Javascript

function reverseInParentheses(inputString) {
    let mainArr = inputString.split('');
    let arrLength = mainArr.length;
    let arr1 = [];
    for(let i = 0; i < arrLength; i++) {
        if(mainArr[i] != ')') {
            arr1.push(mainArr[i]);
        } else {
            let temp = reverseSelectedString(arr1); // call function to reverse selected string
            arr1 = arr1.splice(0, arr1.lastIndexOf("("));
            arr1 = arr1.concat(temp);
        }
    }
    return arr1.join('');
}

function reverseSelectedString(arrFirst) {
    let arr2 = [];
    let arrLength = arrFirst.length;
    for(let j = arrLength; j >= 0; j--) {
        if(arrFirst[j] != '(') {
            arr2.push(arrFirst[j]);
        } else {
            break;
        }
    }
    return arr2;
}

Answer 14

在Javascript/nodejs

//Regex for opening and closing parenthesis
const o_brc = /[\{\[\(]/g;
const c_brc= /[\}\]\)]/g;

const revPar = str => {
  let top =-1;
  let rev_str = [];

  for(let i in str){
    if(c_brc.test(str[i])){

        const rev = [];
        let j = i-1;
        while(rev_str.length){
          if(o_brc.test(rev_str[top])){
            break;
          }
          rev.push( rev_str.pop());
          top--;
        }

        rev_str.pop(); //pop out the opening brackets after reversing
        top--;
        rev_str = [...rev_str, ...rev]; 
        top += rev.length; //increment the top upto rev.length
    }
    else{
      rev_str.push(str[i]); //push to rev_str if not a closing bracket
      top++;
    }
  }

  console.log((rev_str.join('')));

}

Answer 15

这是一个很好的直截了当的 c++ 答案

每当我们看到左括号时，我们就将索引压入堆栈，当我们找到右括号时，我们弹出最后一个索引并反转这两个索引之间的子字符串。然后我们删除额外的括号

string reverseInParentheses(string inputString) {
    
    
  stack<int> index;
   
  for (int i = 0 ; i < inputString.length(); i++){
      if (inputString[i] == '('){
          index.push(i);
      }
      if (inputString[i] == ')'){
          reverse(inputString.begin()+ index.top(), inputString.begin()+i+1);
          index.pop();
      }
    }
    string s = "";
    for (int i = 0; i < inputString.length();i++){
        if (inputString[i] != '(' && inputString[i] != ')'  )
            s += inputString[i];
    }
    
    cout << s << endl;
    return s;
  
  

}

Answer 16

这是 Vahan 答案的修改版本，将正则表达式执行压缩为一个替换调用：

function reverseInParentheses(inputString) {
    regex = /\(([^()]*)\)/i;
    
    if (inputString.includes('(')) {
        return reverseInParentheses(inputString.replace(regex, (_, ) => .split('').reverse().join('')));   
    } else {
        return inputString
    }
}

Answer 17

我的做法是找到配对括号，将括号中的顺序倒过来。最后，使用 filter() 删除所有括号。与其他解决方案相比，该解决方案有点冗长，但我发现我可以更好地遵循这种方法。

function reverseInParentheses(inputString) {
  const stack = [];
  let inputList = inputString.split("");

  for (let i = 0; i < inputList.length; i++) {
    if (inputList[i] === "(") {
      stack.push(i);
    } else if (inputList[i] === ")") {
      const begin = stack.pop();
      const reversedSeq = reverseString(inputList.slice(begin + 1, i));
      appendSubsequence(reversedSeq, inputList, begin + 1);
    }
  }

  return inputList.filter((char) => char !== "(" && char !== ")").join("");
}

const reverseString = (sequence) => {
  for (let i = 0; i < sequence.length / 2; i++) {
    const endIndex = sequence.length - i - 1;
    [sequence[i], sequence[endIndex]] = [sequence[endIndex], sequence[i]];
  }
  return sequence;
};

const appendSubsequence = (sequence, arr, begin) => {
  let counter = 0;

  while (counter < sequence.length) {
    arr[begin++] = sequence[counter++];
  }
};

Answer 18

Simple and easy with DEQUEUE

String reverseInParentheses(String s) {
    Deque dq = new LinkedList<Character>();
    for(int i=0;i<s.length();i++){
        dq.add(s.charAt(i));
        if(s.charAt(i)==')'){
            int k=i-1;
            String temp="";
            dq.removeLast();
            char c1=(char)dq.getLast();
            while(c1!='('){
                temp=temp+dq.removeLast().toString();
                c1=(char)dq.getLast();
            }
            dq.removeLast();
            int c=0;
            while(c<temp.length()){
                dq.add(temp.charAt(c));
                c++;
            }
        }
    }
    String temp="";
    Iterator iteratorVals = dq.iterator();
      
    while (iteratorVals.hasNext()) {
        temp=temp+iteratorVals.next();
    }
    return temp;
}

Answer 19

我无法理解 python 最佳解决方案，所以我不得不将其分成几块来理解。

In Python:

Simple Method

def reverseInParentheses(s):
    return eval('"' + s.replace('(', '"+("').replace(')', '")[::-1]+"') + '"')





s = "abc(def(ghi)klm)nop"
print("original",s)
print("first replace", s.replace('(', '"+("'))
print("second replace", s.replace('(', '"+("').replace(')', '")[::-1]+"'))
print("third step addition",'"' + s.replace('(', '"+("').replace(')', '")[::-1]+"') + '"')
print('final evaluation', eval('"' + s.replace('(', '"+("').replace(')', '")[::-1]+"') + '"'))

输出：

original abc(def(ghi)klm)nop

first replace abc"+("def"+("ghi)klm)nop

second replace abc"+("def"+("ghi")[::-1]+"klm")[::-1]+"nop

third step addition "abc"+("def"+("ghi")[::-1]+"klm")[::-1]+"nop"

final abcmlkghifednop

Answer 20

这是我通过的解决方案：

function extractParenthesesAndKey(input) {
  const match = input.match(/\(([^()]*)\)/i);
  if (!match) return null;
  const result = match[0];
  const key = result.substring(1, result.length - 1);
  return { result, key };
}

function hasParentheses(string) {
    return string.includes('(') || string.includes(')');
}

function solution(inputString) {
    let interpolatedInput = inputString.slice(); // no side-effect
    let itHasParentheses = hasParentheses(interpolatedInput);
    while(itHasParentheses) {
        const extractedData = extractParenthesesAndKey(interpolatedInput);
        interpolatedInput = interpolatedInput.replace(extractedData.result, 
        extractedData.key
          .split('')
          .reverse()
          .join(''));
        solution(interpolatedInput);
        itHasParentheses = hasParentheses(interpolatedInput);
    }
    return interpolatedInput;
}

Answer 21

function solution(inputString) {
    while(inputString.includes('(')){
      inputString =  inputString.replaceAll(/\([a-z]*\)/g, str=>str.split('').slice(1, -1).reverse().join(''));
    }
    return inputString
}

发现此解决方案非常清晰易用

反向括号 - Codefights

ReverseParentheses - Codefights

javascript

reverse

parentheses