変換アルゴリズムかっこ

1761 ワード

//u, v로 분리시키는 함수
//균형만 잡히도록
function seperate(s) {
  let open = 0;
  let close = 0;
  let slice;
  for (let i = 0; i < s.length; i++) {
    if (s[i] === "(") open++;
    else close++;
//균형잡힌 괄호 만나는 순간 index저장해주고 바로 for문 종료시켜준다
    if (open === close) {
      slice = i;
      break;
    }
  }
//index 이용해서 쪼개준 뒤 배열로 return    
  return [s.slice(0, slice + 1), s.slice(slice + 1)];
}

//올바른 괄호인지 판단하는 함수
function isCorrect(s) {
  const stack = [];
    // 스택의 끝이 열린, 현재괄호 닫힌괄호 == 쌍 맞으면 스택에서 제거해주기   
  for (let x of s) {
    if (x===")"&&stack[stack.length-1]==="(") stack.pop();
    // 아니면 맞는 쌍 기다려 주기 위해 stack에 담기 
      else stack.push(x);
  }
    //다 돌아있을 때 stack에 남아있는지 판별
  return stack.length === 0 ? true : false;
}
// 양 끝 제거하고 뒤집는 함수
function flip(s) {
  let answer = "";
//0번, 마지막은 돌지 않게끔    
  for (let i = 1; i < s.length - 1; i++) {
    answer += s[i] === "(" ? ")" : "(";
  }
  return answer;
}

function solution(p) {
  if (p === "") return ""; //재귀 함수 종료시키는 조건
  var answer = "";    
  let seperated = seperate(p);
  
  let u = seperated[0];
  let v = seperated[1];
 
 //올바른 괄호 문자열인지 판별
  if (isCorrect(u)) {
    //계속 재귀함수 실행되서 쪼갰을때 v가 ""일떄  
    v = solution(v);
    return u + v;
  } else {
    //u가 옳지 않은 괄호라면 u는 고정시키고 v만 다시 쪼개나간다  
    v = solution(v);
    //끝까지 쪼개서 v가 ""이면 재귀함수 종료된다.
    //그러면 재귀함수 종료되면 60번 라인으로 넘어가서 정답을 return한다
    answer = "(" + v + ")" + flip(u);
    return answer;
  }
}
理解するために、私はどこにでも注釈をつけました.
1.かっこが正しいかどうかを判断する関数
2.バランスカッコの関数を作成する
3.両端と反転を除去する関数はうまく実現しているが
再帰関数部分は完全に理解されていない.
問題は所定の方法で実施され、解決されたが.
再帰関数がどのように動作するかをもう一度勉強します.