Simple Balanced Parentheses

출처: http://interactivepython.org/courselib/static/pythonds/BasicDS/SimpleBalancedParentheses.html

아래는 괄호를 이용한 연산식이다.

(5+6)∗(7+8)/(4+3)

우리는 여는 괄호가 있으면 닫는 괄호가 반드시 있어야 한다는 것을 잘 알고 있다.

다음은 정상적인(balanced) 괄호 사용의 예이다.

(()()()())
(((())))
(()((())()))

다음은 비정상적인(not balanced) 괄호 사용의 예이다.

((((((())
()))
(()()(()
(()))(
())(()

괄호의 사용이 잘 되었는지 잘못 되었는지 판별 해 주는 프로그램을 작성하시오.

stack
+1 이문제는 제가 티켓몬스터 코딩시험봤을때 출제되었던 문제와 흡사하네요 ^^ - 23king, 2014/10/15 15:26 M D
+2 문제의 '(5+6)∗(7+8)/(4+3)' 와 같이 숫자나 기호가 함께 입력되지 않는다는 가정을 추가한다면 더 명확한 문제가 되겠네요 ^^(저는 이렇게 입력될 수 도 있다는 가정하에 풀이를 하였습니다만 ㅎㅎ;) 그리고, 몇몇분의 풀이 중 괄호 쌍의 개수만 확인하는 경우가 있는데 '())(()' 와 같이 괄호 쌍의 개수는 맞지만 괄호 순서가 맞지 않는 경우도 있으니 이에 신경 써서 풀어 야 할 것 같습니다. - 안 준환, 2014/10/23 01:36 M D
괄호순서가 맞지 않는 경우는 위에서 제시한 4가지 예중 4번째에서 판별이 가능하긴 합니다. - 길가의풀, 2014/10/23 09:21 M D
네 ^^; 그런데 저걸로 체크가 안되는게, 괄호 개수와 가장 좌측,우측의 괄호 체크를 하신분들이 몇몇 계셔서요 ^^ - 안 준환, 2014/10/23 18:17 M D
안 준환님, 비정상적인(not balanced) 괄호 사용의 예에 말씀하신 것을 추가했습니다. (5번째) - 길가의풀, 2014/10/31 14:32 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

58개의 풀이가 있습니다. 1 / 6 Page

def isBalanced(s):
    n=0
    for i in range(len(s)):
        n += (1 if s[i]=='(' else -1)
        if n < 0:
            return False

    return True if n==0 else False

print(isBalanced('(()()()())'))
print(isBalanced('(((())))'))
print(isBalanced('(()((())()))'))
print(isBalanced('((((((())'))
print(isBalanced('()))'))
print(isBalanced('(()()(()'))
print(isBalanced('(()))('))
더이상 간단해지기도 어렵겠군요. 심플하네요 ^^ range(les(s)) 쓰는대신 걍 for c in s: 로 하면 조금 더 간단해 질수는 있겠네요. def isBalanced(s): n=0 for c in s: n += (1 if c=='(' else -1) if n < 0: return False return n==0 - 길가의풀, 2014/09/19 09:55 M D
1과 -1을 더하다가 0보다 작은 경우가 False이군요. 미처 생각을 못했어요^^ - 디디, 2016/03/23 22:58 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

스택(Stack)을 이용해 봤습니다.

import unittest

class Stack:
     def __init__(self):
         self.items = []

     def isEmpty(self):
         return self.items == []

     def push(self, item):
         self.items.append(item)

     def pop(self):
         return self.items.pop()

     def peek(self):
         return self.items[len(self.items)-1]

     def size(self):
         return len(self.items)


def isBalanced(s):
    stack = Stack()
    for c in s:
        if c == "(":
            stack.push(c)
        elif c == ")":
            if stack.isEmpty(): 
                return False
            stack.pop()
    return stack.isEmpty()


class BanlanceTest(unittest.TestCase):
    def test1(self):
        self.assertTrue(isBalanced("(5+6)*(7+8)/(4+3)"))
        self.assertTrue(isBalanced("(()()()())"))
        self.assertTrue(isBalanced("(((())))"))
        self.assertTrue(isBalanced("(()((())()))"))
        self.assertFalse(isBalanced("((((((())"))
        self.assertFalse(isBalanced("()))"))
        self.assertFalse(isBalanced("(()()(()"))
        self.assertFalse(isBalanced("(()))("))


if __name__ == "__main__":
    unittest.main()
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

문제 태그에 답이 떡하니.... 가장 중요한 원칙은 "열었던 괄호는 꼭 닫아야 하고, 열지 않은 괄호는 닫지 말아야 한다"입니다.

따라서 처음이 여는 괄호로 시작해도 안되고 (()))( 와 같이 열고 닫는 순서가 틀려도 안됩니다. (([{]})) 이런 것도 (문제에서는 언급안했지만) 올바르게 닫힌 괄호가 아니죠.

하는 김에 괄호의 종류를 모두 비교하도록 했습니다.

PAIRS = {")": "(", "}": "{", "]": "["}
def isBalanced(s):
    t = []
    for c in [x for x in s if x in "(){}[]"]:
        if c in "({[":
            t.append(c)
        elif t == []:
            return False
        else:
            if t[-1] == PAIRS[c]:
                t.pop()
            else:
                return False
    if t:
        return False
    return True
네, 태그는 주로 힌트나 관련 알고리즘을 적는데요, 대부분 다른 방식으로 푸셨더라구요. ㅎㅎ - 길가의풀, 2014/12/12 23:44 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
def balance(s):
    depth=0
    for c in s:
        if c=='(':depth+=1
        if c==')':depth-=1
        if depth < 0 : return False
    return  depth == 0   
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
#include<iostream>
#include<string>
#include<map>
using namespace std;

bool isBalancedParentheses(string s) {
    static map<string, bool> memo;
    auto iter = memo.find(s);
    if (iter != memo.end()) {
        return iter->second;
    }

    bool &result = memo[s];
    result = false;

    if (s.length() == 0) {
        result = true;
    } else if (s[0] == '(') {
        auto s_it = s.begin();
        for (; ++s_it != s.end();) {
            if (*s_it != ')') {
                continue;
            }

            if (isBalancedParentheses(string(s.begin() + 1, s_it))
                    && isBalancedParentheses(string(s_it + 1, s.end()))) {
                result = true;
                break;
            }
        }
    } else {
        result = false;
    }
    return result;
}

int main() {
    string input;

    while (cin >> input) {
        bool result = isBalancedParentheses(input);
        cout << result << "\n";
    }
    return 0;
}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
def isBalancedParentheses(s):
    init = 0
    for n in map(lambda c:1 if c == '(' else -1, filter(lambda c:False if c != '(' and c != ')' else c, s)):
        init += n
        if init < 0: return False
    if init != 0: return False
    return True

def main():
    print(isBalancedParentheses('(5+6)*(7+8)/(4+3)'))
    print(isBalancedParentheses('(()()()())'))
    print(isBalancedParentheses('(((())))'))
    print(isBalancedParentheses('(()((())()))'))

    print(isBalancedParentheses('((((((())'))
    print(isBalancedParentheses('()))'))
    print(isBalancedParentheses('(()()(()'))
    print(isBalancedParentheses('(()))('))

if __name__ == '__main__':
    main()
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

java 풀이입니다. 안준환님 풀이를 참고하였습니다.

public class SimpleBalancedParentheses {
    public static void main(String[] args) {
        System.out.println("(5+6)∗(7+8)/(4+3) : " + SimpleBalancedParentheses.isBalancedParenthreses("(5+6)∗(7+8)/(4+3)"));
        System.out.println("(()()()())  : " + SimpleBalancedParentheses.isBalancedParenthreses("(()()()())"));
        System.out.println("(((())))    : " + SimpleBalancedParentheses.isBalancedParenthreses("(((())))"));
        System.out.println("(()((())()))    : " + SimpleBalancedParentheses.isBalancedParenthreses("(()((())()))"));

        System.out.println("((((((())   : " + SimpleBalancedParentheses.isBalancedParenthreses("((((((())"));
        System.out.println("()))        : " + SimpleBalancedParentheses.isBalancedParenthreses("()))"));
        System.out.println("(()()(()    : " + SimpleBalancedParentheses.isBalancedParenthreses("(()()(()"));
        System.out.println("(()))(      : " + SimpleBalancedParentheses.isBalancedParenthreses("(()))("));
    }

    public static boolean isBalancedParenthreses(String input) {

        /** 입력 String 유효성 체크 */
        if (input != null && input.equals("") == false) {

            /** 괄호 index 값 */
            int idx = 0;

            /** 입력 String length 만큼 반복 */
            for(int i = 0; i < input.length(); i++) {

                /** 대상 문자 */
                String s = input.substring(i, i+1);

                /** 대상 문자 유효성 체크 */
                if (s != null && s.equals("") == false) {

                    /** 괄호 열림은 +1 */
                    if (s.equals("(")) {
                        idx += 1;
                    } 

                    /** 괄호 닫힘은 -1 */
                    else if(s.equals(")")) {
                        idx -= 1;
                    }
                }

                /** 인덱스 값이 0보다 작다는 것은 열지도 않은 괄호를 닫았다는 것..  */
                if (idx < 0) {
                    return false;
                }
            }

            /** 0이면 정상. 0이 아니라면 괄호를 연 것이 더 많은 경우.. */
            if (idx == 0) {
                return true;
            }

        }

        return false;
    }
}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

C#으로 작성했습니다. 한 줄씩 input을 받아서 List char에 각각 넣고 for loop으로 하나하나 체크해가면서 '(' 일때는 +1, ')' 일때는 -1을 계산하여 총 합이 0이 되면 correct를, 그렇지 않으면 error를 출력합니다.

        public bool ValidateParentheses(string input)
        {
            var count = 0;
            for (int i = 0; i < input.Length; i++ )
            {
                var curr = input[i].ToString();
                if (curr == "(") count++;
                else if (curr == ")") count--;
                if (count < 0) return false;
            }
            return count == 0;
        }
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
String test = "((5+6)(123)(1818))";
Pattern p = Pattern.compile("(\\()|(\\))|([^\\(|\\)])");
Matcher m = p.matcher(test);
System.out.println( (m.replaceAll("$1").length() -m.replaceAll("$2").length() == 0 ? "Yes" : "no"));
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
public class Main {
    public static void main(String[] ar){
        String s = "(((()"; // 입력 생략

        int l = 0;
        int r = 0;

        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == '(')
                l++;
            else if(s.charAt(i) == ')')
                r++;
        }

        if(l != r)
            System.out.println("error!");
        else
            System.out.println("correct!");             
    }
}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

풀이 작성

※ 풀이작성 안내
  • 본문에 코드를 삽입할 경우 에디터 우측 상단의 "코드삽입" 버튼을 이용 해 주세요.
  • 마크다운 문법으로 본문을 작성 해 주세요.
  • 풀이를 읽는 사람들을 위하여 풀이에 대한 설명도 부탁드려요. (아이디어나 사용한 알고리즘 또는 참고한 자료등)
  • 작성한 풀이는 다른 사람(빨간띠 이상)에 의해서 내용이 개선될 수 있습니다.
목록으로
코딩도장

코딩도장은 프로그래밍 문제풀이를 통해서 코딩 실력을 수련(Practice)하는 곳입니다.

stack x 2
연관 문제

언어별 풀이 현황
전 체 x 58
java x 11
scala x 2
python x 28
perl x 1
cs x 2
기 타 x 8
cpp x 5
ruby x 1