変換アルゴリズムかっこ
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.両端と反転を除去する関数はうまく実現しているが
再帰関数部分は完全に理解されていない.
問題は所定の方法で実施され、解決されたが.
再帰関数がどのように動作するかをもう一度勉強します.
Reference
この問題について(変換アルゴリズムかっこ), 我々は、より多くの情報をここで見つけました https://velog.io/@chuhyerin96/알고리즘-괄호변환テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol