출처: http://interactivepython.org/courselib/static/pythonds/BasicDS/SimpleBalancedParentheses.html
아래는 괄호를 이용한 연산식이다.
(5+6)∗(7+8)/(4+3)
우리는 여는 괄호가 있으면 닫는 괄호가 반드시 있어야 한다는 것을 잘 알고 있다.
다음은 정상적인(balanced) 괄호 사용의 예이다.
(()()()())
(((())))
(()((())()))
다음은 비정상적인(not balanced) 괄호 사용의 예이다.
((((((())
()))
(()()(()
(()))(
())(()
괄호의 사용이 잘 되었는지 잘못 되었는지 판별 해 주는 프로그램을 작성하시오.
128개의 풀이가 있습니다.
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('(()))('))
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
스택(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
짧지만 { } [ ] ( ) 세 종류의 괄호 모두와 문자포함된 문자열까지 판별 가능합니다. 닫혀있는 괄호쌍 () [] {}를 연속적으로 제거하여 아무것도 남지않으면 True 남으면 False 입니다. ex) '[1{asd}(as(da[d])ds)]' -> [{}(([]))] -> [(())] ->[()] -> [] -> True
def check_parentheses(x):
import re
y = ''.join([a for a in x if a in list('{}[]()')])
for i in range(len(y)//2): y = re.sub('(\[\])|(\{\})|(\(\))', '', y)
return True if not y else False
결과
print(check_parentheses('[1{asd}(as(da[d])ds)]'))
True
Process finished with exit code 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!");
}
}
3가지의 조건하에 검증이 되네요
'('와 ')'의 갯수가 같을것
처음엔 반드시 '('로 시작할것
마지막은 반드시 ')'로 끝날것
해서 java로 풀어봤습니다.
package coding.test;
public class Validation {
public boolean validation(String text){
if(findParenthesis(text,'(')!=findParenthesis(text,')')){
return false;
}else if(!text.substring(0,1).equals("(")){
return false;
}else if(!text.substring(text.length()-1, text.length()).equals(")")){
return false;
}else{
return true;
}
}
public int findParenthesis(String str,char exp){
int cnt=0;
for( int i=0; i<str.length(); i++)
if(str.charAt(i)==exp) cnt++;
return cnt;
}
public static void main (String args[] )throws Exception{
System.out.println("(()()()()) : "+new Validation().validation("(()()()())"));
System.out.println("(((()))) : "+new Validation().validation("(((())))"));
System.out.println("(()((())())) : "+new Validation().validation("(()((())()))"));
System.out.println("((((((()) : "+new Validation().validation("((((((())"));
System.out.println("())) : "+new Validation().validation("()))"));
System.out.println("(()()(() : "+new Validation().validation("(()()(()"));
System.out.println("(()))( : "+new Validation().validation("(()))("));
}
}
오류가 있어서 수정했습니다.
알고리즘을 조금 바꿔봤습니다
package codingdojang.test465;
public class Test_457 {
public boolean validation(String text){
String tmp=text;
boolean result=true;
while(tmp.length()>0){
try{
if(tmp.startsWith(")")){
result=false;
break;
}
tmp=tmp.substring(0,tmp.indexOf("("))+tmp.substring(tmp.indexOf("(")+1,tmp.length());
tmp=tmp.substring(0,tmp.indexOf(")"))+tmp.substring(tmp.indexOf(")")+1,tmp.length());
}catch(StringIndexOutOfBoundsException e){
result=false;
break;
}
}
return result;
}
public static void main (String args[] )throws Exception{
System.out.println("(()()()()) : "+new Test_457().validation("(()()()())"));
System.out.println("(((()))) : "+new Test_457().validation("(((())))"));
System.out.println("(()((())())) : "+new Test_457().validation("(()((())()))"));
System.out.println("((()((()))())) : "+new Test_457().validation("(()((())()))"));
System.out.println("((((((()) : "+new Test_457().validation("((((((())"));
System.out.println("())) : "+new Test_457().validation("()))"));
System.out.println("(()()(() : "+new Test_457().validation("(()()(()"));
System.out.println("(()))( : "+new Test_457().validation("(()))("));
System.out.println("())(() : "+new Test_457().validation("())(()"));
}
}
c++ 입니다!
#include <iostream>
#include <string>
using namespace std;
bool checkBalancedParentheses(string);
int main(int argc, const char * argv[]) {
cout<<checkBalancedParentheses("(()()()())")<<endl;
cout<<checkBalancedParentheses("(((())))")<<endl;
cout<<checkBalancedParentheses("(()((())()))")<<endl;
cout<<checkBalancedParentheses("((((((())")<<endl;
cout<<checkBalancedParentheses("()))")<<endl;
cout<<checkBalancedParentheses("(()()(()")<<endl;
cout<<checkBalancedParentheses("(()))(")<<endl;
return 0;
}
bool checkBalancedParentheses(string str) {
int count = 0;
for(int i = 0; i < str.length(); i++) {
if(str[i] == '(') ++count;
else if(str[i] == ')')
if(--count < 0) return false;
}
if(count) return false;
return true;
}
결과는
1
1
1
0
0
0
0
Program ended with exit code: 0
이렇게 나오네요. 의외로 쉬운 문제였습니다!
test=['(()()()())',
'(((())))',
'(()((())()))',
'((((((())',
'()))',
'(()()(()',
'(()))(',]
import re
def core(i):
temp=i
while 1:
temp1 = re.sub('\(\)', '', temp)
if temp1 == '':
return True
elif temp1==temp:
return False
else:
temp=temp1
for i in test:
print(i)
print(core(i))
뒷북인가요?
// Java
public class Balanced {
private static int top = -1;
private static final int N = 1000;
public static void main(String[] args) {
System.out.println(validate("(5+6)∗(7+8)/(4+3)"));
System.out.println(validate("(()()()())"));
System.out.println(validate("(((())))"));
System.out.println(validate("(()((())()))"));
System.out.println(validate("((((((())"));
System.out.println(validate("()))"));
System.out.println(validate("(()()(()"));
System.out.println(validate("(()))("));
}
public static String validate(String str) {
top = -1;
try {
for (int i = 0; i < str.length(); i++) {
String s = str.substring(i, i+1);
if ("(".equals(s)) push(s);
if (")".equals(s)) pop();
}
} catch (StackExceptoin e) {
top = -2;
}
return (top == -1) ? "balanced" : "not balanced";
}
public static void push(String str) throws StackExceptoin {
if (top >= N-1) throw new StackExceptoin();
++top;
}
public static void pop() throws StackExceptoin {
if (top < 0) throw new StackExceptoin();
--top;
}
}
class StackExceptoin extends Exception {
private static final long serialVersionUID = 1L;
}
Stack 방식 이용했으나 실제 값 저장 없이 top 값만 조정했습니다.
clojure
(ns balanced.core)
(def BALANCED_OPENER \()
(def BALANCED_CLOSER \))
(defn is-balanced?
[something]
(loop [[fst & rst] something p 0]
(if (neg? p)
false
(if-not fst
(zero? p)
(condp = fst
BALANCED_OPENER (recur rst (inc p))
BALANCED_CLOSER (recur rst (dec p))
(recur rst p))))))
(is-balanced? "(()()()())(((())))(()((())()))")
;=> true
(is-balanced? "((((((())()))(()()(()(()))(())(()")
;=> false
(is-balanced? "(5+6)∗(7+8)/(4+3)")
;=> true
(is-balanced? "(()()()())")
;=> true
(is-balanced? "(((())))")
;=> true
(is-balanced? "(()((())()))")
;=> true
(is-balanced? "((((((())")
;=> false
(is-balanced? "()))")
;=> false
(is-balanced? "(()()(()")
;=> false
(is-balanced? "(()))(")
;=> false
Scala
def balanced(expr: String): Boolean = {
// try {
// expr.foldLeft(0) { (result, c) =>
// if(c == '(') result + 1
// else if(c == ')') {
// if(result > 0)
// result - 1
// else
// throw new IllegalArgumentException
// } else result
// } match {
// case 0 => true
// case _ => false
// }
// } catch {
// case _: Throwable => false
// }
def fn(expr: String, count: Int): Boolean = {
if(expr == "") {
count == 0
} else if(count < 0) {
false
} else {
val head = expr.head
if(head == '(')
fn(expr.tail, count + 1)
else if(head == ')')
fn(expr.tail, count - 1)
else
fn(expr.tail, count)
}
}
fn(expr, 0)
}
"""
(()()()())
(((())))
(()((())()))
((((((())
()))
(()()(()
(()))(
())(()
""".trim.split("\n").foreach { input =>
println(input)
println(balanced(input))
}
def valid?(str)
checksum = 0
str.scan(/[()]/).each do |c|
checksum +=
case c
when "(" then 1
when ")" then -1
end
return false if checksum < 0
end
checksum.zero?
end
def valid_parens(string)
string.scan(/[()]/).
map.with_object([1]){|e, s| e == "(" ? s.push(e) : s.pop}.
eql?([1])
end
valid_parens("(()()()())") # => true
valid_parens("(((())))") # => true
valid_parens("(()((())()))") # => true
valid_parens("((((((())") # => false
valid_parens("()))") # => false
valid_parens("(()()(()") # => false
valid_parens("(()))(") # => false
valid_parens("())(()") # => false
Perl
한글자씩 확인합니다.
while(<>){
my $s=0;
for (unpack("c*",$_)) {
$s++ if $_==40;
$s-- if $_==41;
last if $s<0
}
$s?print "outrageous\n":print "pleasing\n";
}
이미 최적해가 나왔지만 아주 쉽습니다. 스택도 필요 없고 그냥 카운터 하나만 있으면 됩니다.
#include <iostream>
#include <string>
#include <cassert>
bool checkBalance(const std::string &input) {
int paren = 0;
for (auto c : input) {
if (c == '(') {
++paren;
} else if (c == ')') {
--paren;
if (paren < 0)
return false;
}
}
return (paren == 0);
}
int main() {
assert(checkBalance("(()()()())") == true);
assert(checkBalance("(((())))") == true);
assert(checkBalance("(()((())()))") == true);
assert(checkBalance("((((((())") == false);
assert(checkBalance("()))") == false);
assert(checkBalance("(()()(()") == false);
assert(checkBalance("(()))(") == false);
assert(checkBalance("())(()") == false);
}
python 입니다. 리스트 [0]번째와 [-1]번째는 서로 다르고, [0]와 [-1]을 하나씩 빼나가면서 판단을 합니다.
import re
def func(s):
p = re.compile('[^\(\)]')
l = list(p.sub('', s))
while l != [] :
t = l[0]
l = l[1:]
if l == [] or l[-1] == t : print "Incorrect"; break
else : l = l[:-1]
if l == [] : print "Correct"; break
func('(5+6)*(7+8)/(4+3)')
func('(5+6)*(7+8)/4+3)')
func('(5+6*(7+8)/(4+3)')
func('(5+6)*(7+8/(4+3)')
Scala로 풀었습니다.
def isBalanced(str:String)={
val arr = str.map(c => if(c =='(') 1 else if(c==')') -1 else 0)
var sum = 0
arr.forall(i => {sum = sum + i; if(sum == -1) false else true}) && sum == 0
}
'('를 1, ')'를 -1로 치환하고, 처음부터 더해가면서 누적합이 -1인 경우(여는 괄호 없는 닫는 괄호를 발견한 경우)는 없는지, 전체 합이 0인지 확인합니다.
coding by python beginner
import re
def chk(p):
regex = re.compile("[()]")
l1 = ''.join(regex.findall(p))
while l1:
if l1[0] != '(': return False
else:
l1 = l1.replace( '(', '', 1 )
if l1.find(')') == -1: return False
l1 = l1.replace( ')', '', 1 )
return True
print( chk('(5+6)∗(7+8)/(4+3)') )
print( chk('(()()()())') )
print( chk('(((())))') )
print( chk('(()((())()))') )
print( chk('((((((())') )
print( chk('()))') )
print( chk('(()()(()') )
print( chk('(()))(') )
print( chk('())(()') )
java로 작성해보았습니다.
public class SimpleBalancedParentheses {
public boolean checkBalance(String origin){
boolean retBool = false;
if(origin == null || origin.length() == 0) return retBool;
char c;
int checkNum = 0 ;
for(int i = 0; i < origin.length(); i++){
c = origin.charAt(i);
if(c == '(') checkNum++;
if(c == ')') checkNum--;
if(checkNum <0) return retBool;
}
if(checkNum == 0) retBool = true;
return retBool;
}
}
테스트 코드 입니다.
import static org.junit.Assert.*;
import org.junit.Test;
public class SimpleBalancedParenthesesTest {
@Test
public void testBalanced() {
String input1 = "(()()()())";
String input2 = "(((())))";
String input3 = "(()((())()))";
String input4 = "(5+6)∗(7+8)/(4+3)";
SimpleBalancedParentheses sbp = new SimpleBalancedParentheses();
assertTrue(sbp.checkBalance(input1));
assertTrue(sbp.checkBalance(input2));
assertTrue(sbp.checkBalance(input3));
assertTrue(sbp.checkBalance(input4));
}
@Test
public void testImBalanced() {
String input1 = "((((((())";
String input2 = "()))";
String input3 = "(()()(()";
String input4 = "(()))(";
String input5 = "())(()";
SimpleBalancedParentheses sbp = new SimpleBalancedParentheses();
assertFalse(sbp.checkBalance(input1));
assertFalse(sbp.checkBalance(input2));
assertFalse(sbp.checkBalance(input3));
assertFalse(sbp.checkBalance(input4));
assertFalse(sbp.checkBalance(input5));
}
}
Using python Stack처럼 사용할 생각을 못해서 약간 헤맷네요..
def simpleBalanced(a):
s = []
for i in [x for x in a if x in "()"]:
if i == "(":
s.append(i)
elif i == ")":
if s:
s.pop()
else:
return False
if s:
return False
return True
어느순간에든 지금까지 나온 (개수가 )개수 이상이어야 한다. 최종적으로는 (개수랑)개수랑 같다.
def isitokay(r):
count1=0
count2=0
for x in r:
if x =='(':
count1+=1
elif x==')' :
count2+=1
if count1<count2:
return False
break
else:
if count1==count2:
return True
else:
return False
c입니다
#include <stdio.h>
#include <string.h>
int main(void)
{
int i = 0;
int len = 0;
int paren[10];
int top = 0;
int stack[10];
scanf("%s", &paren);
len = strlen(paren);
while (i < len)
{
if (stack[i] == '(')
top++;
else
top--;
if (top < 0)
break;
stack[top] = paren[i];
i++;
}
top == 0 ? printf("Balanced.") : printf("Not balanced.");
return 0;
}
static void exce67()// Simple Balanced Parentheses
{
Scanner scan = new Scanner(System.in);
int cnt = 0, i;
String str = scan.nextLine();
for (i = 0; i < str.length() && cnt >= 0; i++)
{
if (str.charAt(i) == '(')
cnt++;
else if (str.charAt(i) == ')')
cnt--;
}
if (i == str.length())
System.out.println("balanced.");
else
System.out.println("not balanced.");
}
int형 변수 하나 선언해서 초기값 = 0, (가 나오면 ++, )가 나오면 --연산을 해 주었습니다. 정상적으로 열고 닫았다면 해당 변수가 0 이하로 떨어지지 않기때문에 0이하로 떨어지는지 아닌지를 이용하여 괄호 정상배치 여부를 확인하였습니다.
public class main {
public static void main(String[] args) {
String[] sample = {"((((((())", "()))", "(()()()())", "(()()(()", "(((())))", "(()))(", "())(()", "(()((())()))"};
//3, 5, 8번째 배열이 balanced입니다.
String[] temp;
int check=0, offset=0;
for (String in : sample) {
check++;
offset = 0;
if (in.length()%2 == 0) {
temp = in.split("");
for (String co : temp) {
if (offset >=0) {
if (co.equals("(")) {
offset++;
} else {
offset--;
}
}
}
if (offset == 0) {
Print_Result(0, check);
} else {
Print_Result(1, check);
}
} else {
Print_Result(1, check);
}
}
}
private static void Print_Result(int re, int check) {
if (re == 0) {
System.out.println("sample"+check+" is Balanced!!!");
} else {
System.out.println("sample"+check+" is Not Balanced!!!");
}
}
}
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>.
출력결과 :
sample1 is Not Balanced!!!
sample2 is Not Balanced!!!
sample3 is Balanced!!!
sample4 is Not Balanced!!!
sample5 is Balanced!!!
sample6 is Not Balanced!!!
sample7 is Not Balanced!!!
sample8 is Balanced!!!
Swift로 Stack을 이용하여 풀어보았습니다.
enum BracketError: ErrorType {
case NotBalanced(brackets: String)
case NotExistedBracket(brackets: String)
}
func isOpenCloseBracket(openBracket: String)(_ closeBracket: String) -> Bool {
switch (openBracket, closeBracket) {
case ("{", "}"), ("[", "]"), ("(", ")"): return true
default: return false
}
}
func checkBracket(brackets: String, var stack: [String] = []) throws {
for bracket in brackets.characters {
let token = String(bracket)
switch token {
case "{", "[", "(":
stack += [token]
case "}", "]", ")":
if stack.isEmpty || !isOpenCloseBracket(stack.removeLast())(token) {
throw BracketError.NotBalanced(brackets: brackets)
}
default:
throw BracketError.NotExistedBracket(brackets: brackets)
}
}
if !stack.isEmpty { throw BracketError.NotBalanced(brackets: brackets) }
}
do {
try checkBracket("(()()()())")
try checkBracket("(((())))")
try checkBracket("(()((())()))")
try checkBracket("((((((())")
try checkBracket("()))")
try checkBracket("(()()(()")
try checkBracket("(()))(")
try checkBracket("())(()")
} catch BracketError.NotBalanced(let brackets) {
print(brackets)
} catch BracketError.NotExistedBracket(let brackets) {
print(brackets)
} catch {
print(error)
}
def balance(s):
n = 0
for c in s:
if c == '(': n += 1
else: n -= 1
if n < 0: return False
if n == 0: return True
else: return False
#include <string>
bool isValid(const char* str)
{
//1. 좌괄호는 반드시 우괄호보다 갯수가 많다.
//2. 좌/우 괄호쌍은 반드시 갯수가 같아야한다.
int count = 0;
int len = strlen(str);
for(int i=0;i<len;i++)
{
if(str[i] == '(')
count++;
if(str[i] == ')')
count--;
if(count < 0)
return false;
}
if(count == 0)
return true;
return false;
}
int main()
{
printf("%d\n",isValid("(5+6)*(7+8)/(4+3)"));
printf("%d\n",isValid("(()()()())"));
printf("%d\n",isValid("(((())))"));
printf("%d\n",isValid("(()((())()))"));
printf("%d\n",isValid("((((((())"));
printf("%d\n",isValid("()))"));
printf("%d\n",isValid("(()()(()"));
printf("%d\n",isValid("(()))("));
printf("%d\n",isValid("())(()"));
return 0;
}
# -*- coding: cp949 -*-
def isBalanced(s):
p=0
for c in s:
if c=='(':p+=1
else:p-=1
if p<0:return False
if p==0:return True
return False
def isBalanced2(s):
p=0
for c in s:
p+= (1 if c=='(' else -1)
if p<0:return False
return True if p==0 else False
def isBalanced3(s): #괄호안에 다른게 있을경우도 생각
p=0
for c in filter(lambda x:x=='('or x==')',s):
p+= (1 if c=='(' else -1)
if p<0:return False
return True if p==0 else False
parentheses="((4+3)*2+3)+(3+2)*4"
print isBalanced3(parentheses)
def checkBracket(value) :
c=0
for i in str(value) :
if i == '(' : c+=1
if i == ')' : c-=1
return c == 0
a = "(5+6)∗(7+8)/(4+3)"
b = "((((((())"
print(checkBracket(a))
print(checkBracket(b))
C# 입니다.
static Dictionary<char, char> cParenRe =
new Dictionary<char, char>() { { ')', '(' }, { '>', '<' }, { ']', '[' }, { '}', '{' } };
static void Main(string[] args)
{
string line = "(({{{(5-7)}<(6*7)/40>}}[{(34-55)*6}*{23+<34*(45-8)>}]))";
Console.WriteLine(CheckParenthesis(line));
}
static bool CheckParenthesis(string line)
{
Stack<char> sParen = new Stack<char>();
for (int i = 0; i < line.Length; i++)
{
if (cParenRe.ContainsValue(line[i])) sParen.Push(line[i]);
else if (cParenRe.ContainsKey(line[i]))
{
if (sParen.Count == 0) return false;
if (cParenRe[line[i]] != sParen.Pop()) return false;
}
}
if (sParen.Count == 0) return true;
else return false;
}
Stack과 Dictionary를 활용하여 구현해봤습니다. 사실 여기서 더 나아가자면 큰 따옴표나 작은 따옴표도 체크 해야되고 그 안에 있는 문자열의 괄호는 제외해야되지만, 여기까지만 타협했습니다 ㅎㅎ.. 딕보다는 ASCII 코드로 가감하여 구하는 방법도 생각해봤는데, 문제는 괄호의 ASCII 코드가 모두 쌍으로 붙어 있지 않아서 패스 했습니다. 딕의 포함 값을 돌리는 방법과 "(<{[".Contains 를 사용하는 방법이 있었는데 수행시간은 딕의 포함값을 돌리는게 몇배나 빠른결과를 보여줘서 딕으로 돌렸습니다. 포함 키가 아닌 포함 값은 루프를 돌려서 검색하는것 같습니다. 첫번째 포함 값은 포함키 만큼 빠르지만, 마지막으로 갈수록 느린 결과를 보여주네요. 물론 지금의 경우는 속도 차이는 사실 거의없습니다. 딕셔너리엔 괄호를 키와 값을 반대로 해서 넣었는데, 나중에 Stack.Pop의 결과와 간단히 비교하기 위해서 입니다.
#인접한 괄호를 하나씩 지우자: 지우는 조건 -> 인접한 괄호가 여는 괄호/ 닫는 괄호순이면, 최종적으로 남는괄호가 없으면 ballanced!!
#'('-> 2 ')'-> 1 인접한 괄호를 끼리 나누어 (/) 2가 나오면 지운다 )/)->1 지울수 없음,(/(-> 1지울수 없음,)/( 1/2 -> 지울수 없음
def convDigit(c):
if c=='(':
return 2
elif c==')':
return 1
def isWellFormed(s):
l=map(convDigit,s.replace(' ',''))
findItems=True
while(findItems):
findItems=False
for i in range(1,len(l)):
if l[i-1]/l[i]==2:
del l[i-1:i+1]
findItems=True
break;
return len(l)==0
############
f1="((((((())"
f2="()))"
f3="(()()(()"
f4="(()))("
f5="())(()"
f6=")("
f6="())(())"
s1="(()()()())"
s2="(((())))"
s3="(()((())()))"
s4="(( )() ((())) ((())()))"
s5="(()(()((()()()()))()))"
print isWellFormed(f1),isWellFormed(f3),isWellFormed(f3),isWellFormed(f4),isWellFormed(f5),isWellFormed(f6),isWellFormed(f7)
print isWellFormed(s1),isWellFormed(s2),isWellFormed(s3),isWellFormed(s4),isWellFormed(s5)
boolean balancedParentheses(String s) {
Stack<Character> stack = new Stack<Character>();
for(int i=0; i<s.length(); i++) {
if(s.charAt(i) == '(') {
stack.push(s.charAt(i));
}
else {
if(stack.empty()) return false;
stack.pop();
}
}
return stack.empty();
}
java
파이썬3.4입니다.
쉬울거 같았는데 의외로 시간을 많이 소비했어요.
서로 인접한 '()'를 제거해주고, 제거된 새로운 문자열을 다시 함수 인자로 넘기는 재귀함수를 사용했어요.
def fnc(s):
if not s:
print('True')
return
elif s.find('()') == -1: #find()는 일치하는 문자열이 없는 경우 -1를 반환.
print('False')
return
s = s.replace('()', '') #인접한 문자열이 '()'인 경우 ''로 치환
fnc(s)
fnc('(()()()())') #True
fnc('())))') #False
시간이 지나 다시 짜보았어요.
def f(s):
while '()' in s:
s = s.replace(' ', '').replace('()', '')
return False if s else True
f('(()()())') #True
f('())))') #False
f('(( )() ((())) ((())) ())') #True
그러나... 공백까지는 어떻게 되겠지만, 공백외에 것들이 있다면 틀린 답이였네요.
상파님 코드 참고해서 다시 수정했어요. 이것이 가장 적당한 답인것 같아요.
def f(s):
depth = 0
for i in s:
if i is '(': depth += 1
elif i is ')': depth -= 1
return not depth
f("(5+6)*(7+8)/(4+3)") #True
Ruby
문자열을 스택으로 사용.
is_balanced = ->str { str.scan(/[()]/).reduce("v") {|a,e| e=='('? a+e : a.chop} == "v" }
Test
# test data
test_str = "(5+6)∗(7+8)/(4+3)"
balanced_strs = %w[ (()()()()) (((()))) (()((())())) ]
not_balanced_strs = %w[ ((((((()) ())) (()()(() (()))( ())(() ]
# test case
expect(is_balanced[test_str]).to eq true
expect(balanced_strs.map &is_balanced).to eq [true]*3
expect(not_balanced_strs.map &is_balanced).to eq [false]*5
Python 2.7
s = raw_input()
paren = 0
for c in s:
if c == '(':
paren+= 1
elif c == ')':
paren-= 1
if paren < 0:
break
print paren == 0
자바로 작성한 코드입니다. 메소드만 공개합니다. (에 대해서 +1카운트, ) -1카운트를 하면서 체크하는 메소드입니다 그러나 카운트값이 -1이 되면 비정상적인 경우이기 때문에 바로 return false로 반환하게 됩니다.
public boolean checkParenthese(String str) {
int count_p = 0;
for (int i = 0; i < str.length(); i++) {
if (str.codePointAt(i) == '(') {
count_p++;
} else if (str.codePointAt(i) == ')') {
count_p--;
} else
continue;
if(count_p < 0 )
return false;
}
if (count_p != 0)
return false;
else
return true;
}
#파이썬 3.5.1
def do(s):
c = 0
for i in s:
if i == '(':
c += 1
elif i == ')':
c -= 1
if c == 0 and s[0] != ')' and s[-1] != '(':
return True
else:
return False
while True:
i = input()
if i == '':
break
else:
print(do(i))
Python 3.4.4
def simple_balanced(data):
state = 0
for x in data:
state += (1 if x == "(" else -1)
if state < 0:
return False
return True if state == 0 else False
print(simple_balanced("(()()()())"))
print(simple_balanced("(((())))"))
print(simple_balanced("(()((())()))"))
print(simple_balanced("((((((())"))
print(simple_balanced("()))"))
print(simple_balanced("(()()(()"))
print(simple_balanced("(()))("))
print(simple_balanced("())(()"))
>>> b = lambda s: s.replace('()', '') == '' or (s.replace('()', '') != s and b(s.replace('()', '')))
>>> b('(()()()())')
True
>>> b('((((((())')
False
>>> b('(()((())()))')
True
>>> b('(((())))')
True
>>> b('(()))(')
False
스택을 이용한 클래식한 문제. 시간복잡도 O(n)의 C++ 코드입니다.
#include <iostream>
#include <cstdlib>
#include <stack>
#include <string>
using namespace std;
int main(){
string s;
cin >> s;
stack<char> st;
for (int i = 0; i < s.size(); i++){
if (s[i] == '(') st.push(s[i]);
else if (s[i] == ')'){
if (st.empty()){
cout << "not balanced" << endl;
return 0;
}else st.pop();
}
}
cout << (st.empty() ? "balanced" : "not balanced") << endl;
return 0;
}
def f(x):
if x.count('(') == x.count(')'):
a, b = 0, 0
for i in x:
if i == '(':
a += 1
else:
b += 1
if b > a:
return False
return True
else:
return False
while __name__ == '__main__':
print(f(input('>>>')))
파이썬 3.5.1
import re
def SBP(x):
parentheses=''.join(re.findall('\(|\)',x))
while re.search('\(\)',parentheses):
parentheses=re.sub('\(\)','',parentheses)
if len(parentheses)==0:
return True
else:
return False
if __name__=='__main__':
print(SBP('(()()()())'))
print(SBP('(((())))'))
print(SBP('(()((())()))'))
print(SBP('((((((())'))
print(SBP('()))'))
print(SBP('(()()(()'))
print(SBP('(()))('))
print(SBP('())(()'))
class balanse{
char[] bal;
int cnt = 0;
boolean bool = true;
balanse(String a){
bal = a.toCharArray();
for(int i = 0; i<bal.length;i++){
if(bal[i]=='(') cnt ++;
else if ( bal[i] ==')') cnt--;
if(cnt<0){
System.out.println("Unbalanse");
break;
}
}
if(cnt==0) System.out.println("Balanse");
else if(cnt>0) System.out.println("Unbalanse");
}
}
public class lv2_10 {
public static void main(String[] args) {
// TODO Auto-generated method stub
String a = "(5+6)*(7+8)/(4+3)";
balanse b = new balanse(a);
b = new balanse("(()))(");
}
}
def checker_parenthese(string):
checker = 0
for i in range(len(string)):
if string[i] == "(":
checker +=1
else:
checker -= 1
if checker < 0 :
return False
if checker == 0 :
return True
else:
return False
#result : True
print checker_parenthese("(()()()())")
print checker_parenthese("(((())))")
print checker_parenthese("(()((())()))")
#result : False
print checker_parenthese("((((((())")
print checker_parenthese("()))")
print checker_parenthese("(()()(()")
print checker_parenthese("()))(")
def bal_parent(st):
in_lst, out_lst = [], []
for i,s in enumerate(st):
if s == '(':
in_lst.append(i)
elif s == ')':
out_lst.append(i)
for i in range(len(in_lst)):
if len(out_lst) == i or in_lst[i] > out_lst[i]:
return False
return True
strn=[
'(()()()())',
'(((())))',
'(()((())()))',
'((((((())',
'()))',
'(()()(()',
'(()))(',
'())(()',
'())(()'
]
for st in strn:
print(bal_parent(st))
다른 분들에 비해 많이 부족하네요..
import re
def check_(str_):
str_ = re.sub(r'((?<!\\)([\'"])[^\n]*?(?<!\\)\2)', '', str_) #문자열 제거
stack = []
for c in str_:
if c == "(":
stack.append("(")
elif c == ")":
if len(stack) != 0:
stack.pop()
else:
return False
return len(stack) == 0
print(check_('(5+6)∗(7+8)/(4+3)'))
print(check_('(()()()())'))
print(check_('(((())))'))
print(check_('(()((())()))'))
print(check_('((((((())'))
print(check_('()))'))
print(check_('(()()(()'))
print(check_('(()))('))
print(check_('())(()'))
Python 3.5.2에서 작성하였습니다.
int main() { char paren[256]; int i, open = 0; fgets(paren, sizeof(paren), stdin); paren[strlen(paren)-1] = '\0';
for (i = 0; i < strlen(paren); i++) {
if (paren[i] == '(') open++;
else if (open == 0) { printf("X\n"); return 0; }
else open--;
}
if (open != 0) { printf("X\n"); return 0; }
else { printf("O\n"); return 0; }
}
#python 2.7
question = list('(()()()())(())(((((')
stack =[]
for x in question:
try:
if x == '(':
stack.append('check')
else:
stack.pop()
except:
print "Its' Wrong!"
if len(stack) != 0:
print "It's Wrong!"
else:
print "Its Okay!"
스텍을 사용하면 간단하게 풀수 있어요 ~
파이썬3 입니다.
input_str = input('연산식을 입력하세요: ')
check = 0
for i in range(len(input_str)):
if input_str[i] == '(':
check += 1
if input_str[i] == ')':
check += -1
if check == -1:
print('wrong')
break
if i == len(input_str)-1 and check != 0:
print('wrong')
break
if i == len(input_str)-1 and check == 0:
print('correct')
def chk_balance(test):
if test.count('(') != test.count(')'):
return 'no balanced'
bool_list = list()
for x in test:
if x == '(':
bool_list.append(1)
elif x == ')' and len(bool_list) != 0:
bool_list.pop(0)
else:
return 'no balanced'
return 'balanced'
#### 2016.12.30 D-419 ####
#include <stdio.h>
#include <string.h>
void main() {
char str[] = "(()))(";
int size = strlen(str);
int n = 0;
for(int i=0;i<size;i++) {
if(str[i]=='(')
n++;
else
n--;
if(n>0)
break;
}
if(n==0)
printf("true\n");
else
printf("false\n");
}
def fn(a):
a=list(i for i in a)
tmp=list()
count=0
for i in a:
if i=='(':
tmp.append(i)
count+=1
elif i==')':
if len(tmp) > 0: tmp.pop()
count-=1
if count < 0: return False
return True if count==0 else False
print(fn('(()()()())'))
print(fn('(((())))'))
print(fn('(()((())()))'))
print(fn('((((((())'))
print(fn('()))'))
print(fn('(()()(()'))
print(fn('(()))('))
def balanced_blanket(data):
data=list(data)
for i in range(int(len(data)/2)):
for j in range(len(data)-1):
if data[j:j+2] in [['(',')'],['{','}'],['[',']']]:
del data[j:j+2]
break
return len(data)==0
balanced_blanket("((){})")
import java.util.Scanner;
import java.util.Stack;
import static java.lang.System.in;
public class SimpleBalancedParentheses {
public static void main(String[] args) {
Scanner sc = new Scanner(in);
while (sc.hasNext()) {
String[] i = sc.next().split("");
balanced(i);
}
}
private static void balanced(String[] i) {
Stack<String> s = new Stack();
for (int j = 0; j < i.length; j++) {
if (s.empty()) {
s.push(i[j]);
} else {
if (s.firstElement().equals(i[j])) {
s.push(i[j]);
} else {
if(s.firstElement().equals("("))
s.pop();
}
}
}
System.out.println(s.empty() ? "정상" : "비정상");
}
}
python 3.6, 재귀함수로 돌렸습니다. () 가 사라질때 까지.
def check_parentheses_rule(example):
chk = ''.join(example.split("()"))
if chk.count("()") != 0:
check_parentheses_rule(chk)
elif len(chk) == 0:
return print("Balanced")
else:
return print("Not Balanced")
결과
>>> check_parentheses_rule('(()()()())')
Balanced
>>> check_parentheses_rule('(((())))')
Balanced
>>> check_parentheses_rule('(()((())()))')
Balanced
>>> check_parentheses_rule('((((((())')
Not Balanced
>>> check_parentheses_rule('()))')
Not Balanced
>>> check_parentheses_rule('(()()(()')
Not Balanced
>>> check_parentheses_rule('(()))(')
Not Balanced
>>> check_parentheses_rule('())(()')
Not Balanced
//괄호의 수가 짝수이다.
//첫번째는 무조건 '(' 제일 뒤는 무조건 ')'
//')'를 찾으면 좌측부터 '('의 수를 조사하고 ')'의 수를 세고
//'('의 수보다 ')'가 커서는 안된다.
public static void main(String[] args) {
System.out.print("연산식을 입력하세요");
String a =new Scanner(System.in).nextLine();
LinkedList<Character> list = new LinkedList<>();// '(' ,')'를 보관할 컬렉션
for(int i=0;i<a.length();i++)
if(a.charAt(i)=='(' || a.charAt(i)==')')
list.add(a.charAt(i)); // '(' ,')' 를 제외하고 모두 제거
boolean answer = false;
if(list.get(0)=='(' && list.getLast()==')') //첫번째 조건 판별
if(list.size()%2==0) //두번째 조건 판별
for(int i=0;i<list.size();i++){
int cnt1=0;
int cnt2=0; //세번째 조건 판별
for(int j=0;j<=i;j++)
if(list.get(j)=='(')cnt1++;
for(int j=0;j<=i;j++)
if(list.get(j)==')')cnt2++;
if(cnt1<cnt2){
answer=false;
break;
}
else
answer=true;
}
System.out.println(answer); //답출력
}
javascript
var balanced = function(parens) {
var stack = 0;
var pushpop = { "(" : 1, ")" : -1 };
for (p of parens.split("")) {
stack += pushpop[p];
if (stack < 0) return false;
}
return stack === 0;
};
// true
console.log(balanced("(()()()())"));
console.log(balanced("(((())))"));
console.log(balanced("(()((())()))"));
// false
console.log(balanced("((((((())"));
console.log(balanced("()))"));
console.log(balanced("(()()(()"));
console.log(balanced("(()))("));
console.log(balanced("())(()"));
초보자 입니다...
filenm = (input("수식을 넣어 주세요 : "))
count1 = 0
count2 = 0
for i in str(filenm):
if i == "(":
count1 += 1
elif i ==")":
count2 += 1
if count1 == count2 :
print("정상입니다.")
else :
print("괄호수가 맞지 않습니다.")
def is_balanced(exp):
depth = 0
for p in exp:
depth += (p=='(') - (p==')')
if depth < 0:
return False
return depth is 0
input = ['(()()()())', '(((())))', '(()((())()))',
'((((((())', '()))', '(()()(()', '(()))(', '())(()']
for exp in input:
print(is_balanced(exp))
f(char*s){
int t=0;
while(*s)
if(*s++-41)t++;
else if(!t)return 0;
else t--;
return !t;
}
C로 숏코딩을 한번 도전해보았습니다~ 개행은 보기쉽도록 제거하지 않았어요.
이 f라는 함수는 NULL로 끝나는 string을 받아서 괄호배치가 올바르면 1, 그렇지 않으면 0을 return합니다. C에서는 함수앞에 type이 없으면 int로 해석하니 일부러 생략했어요. 풀이방식은 스택과 매우 흡사합니다.
넷째줄 연산 우선순위가 약간 암호같은데,, C의 우선순위에 따르면 ((*(s++))-41) 이라서 적절하게 계산됩니다~ 여기서 41은 아스키코드로 ')'를 의미하므로 넷째줄을 직역하면, "현재 문자가 ) 가 아니면 다음문자로 넘어간 뒤 t++해라" 가 돼요.
이 함수는 빈 string(NULL만 존재)에 대해서도 참으로 해석하는데 상식적으로 괄호가 없는데 검사할 필요는 없으니 참으로 해도 되겠죠?^^
Python 3으로 풀었습니다. 괄호가 () 뿐이어서, 단순하게 해결되었네요.
def is_balanced(s):
stack = []
for c in s:
if c == '(':
stack.append(c)
elif not stack:
return False
else:
stack.pop(-1)
return False if stack else True
public static boolean isBalanced(String str) {
int cnt=0;
for(int i=0; i<str.length(); i++) {
if(str.charAt(i) == '(') cnt++;
else if(str.charAt(i) == ')') cnt--;
}
if(cnt!=0) return false;
return true;
}
C
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(int argc, char* argv[])
{
if(argc != 1)
{
printf("argc only 1");
return 0;
}
char* str = (char*)malloc(sizeof(char)*64);
gets(str);
int jwacount = 0;
int woocount = 0;
for(int i=0;i<strlen(str);i++)
{
if(str[i]=='(')
jwacount++;
if(str[i]==')')
woocount++;
}
if(jwacount==0 && woocount==0)
printf("no exist !\n");
else if(jwacount==woocount)
{
printf("correct\n");
}
else
printf("incorrect\n");
}
def simpleBalanced(str):
arr = [x for x in str if x == '(' or x == ')']
for idx1, char1 in enumerate(arr):
for idx2, char2 in enumerate(arr):
if char1 == '(' and idx1<idx2 and char2 == ')':
arr[idx1] = ''
arr[idx2] = ''
break
if len([x for x in arr if x!='']) > 0:
print('false')
else:
print('true')
simpleBalanced('(5+6)∗(7+8)/(4+3)')
simpleBalanced('(()()()())')
simpleBalanced('(((())))')
simpleBalanced('(()((())()))')
simpleBalanced('((((((())')
simpleBalanced('()))')
simpleBalanced('(()()(()')
simpleBalanced('(()))(')
simpleBalanced('())(()')
#include <iostream>
#include <string>
using namespace std;
int main() {
string bracket="(())()()";
int check = 0;
for (char item : bracket) {
if (check < 0) break;
if (item == '(') check++;
else if (item == ')') check--;
//cout << check << endl;
}
if (check==0) cout << "OK" << endl;
else cout << "NO" << endl;
return 0;
}
# python 3.6
inp = ["(()()()())", "(((())))", "(()((())()))",
"((((((())", "()))", "(()()(()", "(()))(", "())(()"]
def chk_bracket(string):
balance = 0
check = True
for c in string:
if c == "(":
balance += 1
elif c == ")":
balance -= 1
if balance < 0:
check = False
break
if balance != 0:
check = False
return check
for s in inp:
print(s, chk_bracket(s))
package codingdojang;
import java.util.ArrayList;
public class ex67 {
public static void main(String[] args) {
// TODO Auto-generated method stub
String parse = "(5+6)*(7+8)/(4+3)";
ArrayList<Character> a = new ArrayList<Character>();
int stack = 0;
for(int i=0; i<parse.length(); i++) {
a.add(parse.charAt(i));
}
for(int i=0; i<a.size()-1; i++) {
for(int j=i+1; j<a.size(); j++) {
if(a.get(i) == '(' && a.get(j) == ')') {
a.set(i, ' ');
a.set(j, ' ');
}
}
}
for(int i=0; i<a.size(); i++) {
System.out.print(a.get(i));
}
System.out.println();
for(int i=0; i<a.size(); i++) {
if(a.get(i) == '(') {System.out.println("비정상적"); return;}
else if(a.get(i) == ')') {System.out.println("비정상적"); return;}
}
System.out.println("정상적");
}
}
def check(char):
opened = 0
closed = 0
result =0
for ch in char :
if ch == "(" : opened += 1
elif ch == ")" : closed += 1
if closed > opened : result +=1 ; break
if char.count("(") != char.count(")") : result +=1
if result == 0 : print("Balanced")
else : print("Unbalanced")
check('(()()(()')
python 3.52입니다
from re import sub
def bal(s):
tmp=list(sub(r'[^()]','',s))
if len(tmp)%2: return(False)
def inner(l):
if l[0]==')' or l.count('(')!=l.count(')'): return(False)
l.remove('(')
l.remove(')')
if not l: return(True)
else: return(inner(l))
return(inner(tmp))
sym=input()
print(bal(sym))
Dictionary 를 이용해서 해봤습니다.
def check(str):
dic = {"(":str.count("("),")":str.count(")")}
return True if (dic["("] == dic[")"]) else False
check("()()()(")
a=input()
c=[]
f=0
for i in a:
if i=='(':
c.append(i)
f=f+1
elif len(c)>0 and i==')':
c.pop()
f=f-1
elif len(c)<=0 and i==')':
f=f-1
if len(c)==0 and f==0:print('True')
else:print('False')
파이썬 3.6
아이디어>
1.처음 괄호가 '(' , 마지막 괄호가 ')'인지 확인
2.동일한 방향으로 반복 사용된 횟수만큼 반대 방향으로 동일한 횟수만큼 사용되었는지 확인하되, 단계별로 괄호를 연 횟수보다 닫은 횟수가 많은지도 함께 확인
def Balanced(ex):
ex_list = list(ex)
if ex_list[0] == '(' and ex_list[len(ex_list)-1] == ')': # 가장 바깥 괄호가 정상인지 확인
m,n = 0,0
for i in range(1,len(ex_list)-1): # 괄호를 연 횟수와 닫은 횟수 카운팅
if ex_list[i] == '(': m += 1
else: n += 1
# 괄호를 연 횟수와 닫은 횟수가 같아지면 카운팅 초기화
if m == n: m,n = 0,0
# 괄호를 연 횟수보다 닫은 횟수가 많은지 확인
if i > 1 and n > m: return "Incorrect Use"
# 괄호를 연만큼 닫았는지 확인
if m == 0 and n == 0 : return "Correct Use"
else: return "Incorrect Use"
else: return "Incorrect Use"
if __name__ == "__main__":
exlist =['(()()()())','(((())))','(()((())()))','((((((())','()))','(()()(()','(()))(','())(()']
for ex in exlist:
print(ex, Balanced(ex))
(()()()()) Correct Use
(((()))) Correct Use
(()((())())) Correct Use
((((((()) Incorrect Use
())) Incorrect Use
(()()(() Incorrect Use
(()))( Incorrect Use
())(() Incorrect Use
# 파이썬
input_sample1 = ["(()()()())", "(((())))", "(()((())()))"]
input_sample2 = ["((((((())", "()))", "(()()(()", "(()))(", "())(()"]
def balanced_parentheses(s1):
left_right = 0
for m in s1:
if m == "(": left_right += 1
elif m == ")": left_right -= 1
if left_right < 0: return "not balanced"
if left_right != 0: return "not balanced"
else: return "balanced"
for m in input_sample1 + input_sample2:
print(balanced_parentheses(m))
def parentheses(a):
if any([a[:i].count('(') < a[:i].count(')') for i in range(1,len(a))]) or a.count('(') != a.count(')'):
return "not balanced"
else:
return "balanced"
print(parentheses(input()))
def Check():
for_check_str=input("판별하려는 문자열을 입력하세요:")
if for_check_str[0]!='(':
return False
counter_a=0 # ( 갯수
counter_b=0 # ) 갯수
if len(for_check_str)%2==0:
for string in for_check_str:
if string=='(':
counter_a+=1
elif string==')':
counter_b+=1
if counter_a<counter_b:
return False
if counter_a==counter_b:
return True
else:
return False
print(Check())
def parentheses(bracket):
opened = 0
for char in bracket:
if char == '(': opened = opened + 1
else:
if opened: opened = opened - 1
if opened: return False
else: return True
파이썬 3.6.4
def bal_par(parentheses) :
count = 0
for i in parentheses :
if i == '(' :
count += 1
else :
count -= 1
if count < 0 :
print('Not balanced')
break
if count == 0 :
print('Balanced')
elif count > 0 :
print('Not balanced')
Swift입니다. (는 +1, )는 -1로 하고, 왼쪽에서 오른쪽으로 계산을 하는데, 중간에 음수가 되거나, 즉 열리지 않았는데, 닫거나, 전체 합이 0이 아니면 False로 계산했습니다.
import Foundation
func checkParentheses(_ inputPattern: String) -> Bool {
return inputPattern.reduce(0, {
if $0 < 0 {
return -1
} else {
return $0 + ($1 == "(" ? 1 : ($1 == ")" ? -1 : 0))
}
}) == 0
}
print(checkParentheses("((a + b) * (c * d)-(a - b) * (a * d) - 1)"))
print(checkParentheses("(((())))"))
print(checkParentheses("(()((())()))"))
print(checkParentheses("((((((())"))
print(checkParentheses("()))"))
print(checkParentheses("(()()(()"))
print(checkParentheses("(()))("))
print(checkParentheses("())(()"))
import java.util.Scanner;
public class test{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int count1=0,count2=0;
System.out.print("Enter : ");
String input = sc.nextLine();
for(int i =0;i<input.length();i++){
if(input.charAt(i) == '(')
count1++;
else if(input.charAt(i) == ')')
count2++;
if(count1<count2){
System.out.println("Error");
break;
}
if(i == input.length()-1 && count1==count2)
System.out.println("Correct");
else if(i == input.length()-1 && count1!=count2){
System.out.println("Error");
break;
}
}
}
}
#Simple Balanced Parentheses
user_input = input()
def isbalanced(string):
# 양 끝을 체크
first = string[0]
final = string[-1]
result = True
if first + final != '()':
result = False
return result
# )의 개수가 (보다 클 수 없음 (좌측을 기준으로)
count_1 = 0 # (
count_2 = 0 # )
for character in string:
if character == '(':
count_1 += 1
elif character == ')':
count_2 += 1
if count_2 > count_1:
result = False
return result
break
# (의 개수가 ) 보다 클 수 없음 (우측을 기준으로)
count_11 = 0 # (
count_22 = 0 # )
for character in string[::-1]:
if character == '(':
count_11 += 1
elif character == ')':
count_22 += 1
if count_1 > count_2:
result = False
return result
break
return result
print(isbalanced(user_input))
def balance(string):
mylist = []
for s in string :
if s =="(" or s ==")": mylist.append(s)
mystr = "".join(mylist)
if mylist.count("(") != mylist.count(")") : return "WRONG"
elif mystr.startswith(")") or mystr.endswith("(") : return "WRONG"
else :
for i in range(0,len(mylist),2):
for j in mylist[:i]:
if mylist[:i].count("(") == mylist[:i].count(")") and mylist[i] == ")" : return "WRONG"
Python
test = ["(()()()())", "(((())))", "(()((())()))", "((())", "((((((())","(()))(","())(()"]
for t in test:
if t.count("(") != t.count(")"):
print("Not Balanced")
continue
while len(t) > 0:
for i in range(len(t)-1):
if t[i:i+2] == "()":
t = t[:i]+t[i+2:]
break
else:
print("Not Balanced")
break
else:
print("Balanced")
리스트를 스택처럼 활용해 대중소괄호 풀어봤습니다~~
data = '''\
(()()()())
(((())))
(()((())()))
((((((())
()))
(()()(()
(()))(
())(()
))(('''
dict1 = {')':'(', ']':'[', '}':'{'}
def balance_test(line, a=[]):
for c in line:
try:
if c in '([{': a.append(c)
elif c in ')]}' and dict1[c] == a[-1]: a.pop()
except: return False
return not a
for line in data.split("\n"):
print(balance_test(line))
괄호 이외의 문자열이 들어간다면 정규표현식이 추가되어야 하겠지만, 괄호 쌍의 정상 유무만 판단한다면 replace 함수로 쉽게 구현됩니다.
def is_balanced(brackets):
result = brackets
while "()" in result:
result = result.replace("()", "")
if result == "":
return True
else:
return False
string = input()
print(is_balanced(string))
def isbalpar(s):
tmp = 0
for i in s:
tmp += (1,-1)[i==')']
if tmp < 0: return False
return tmp==0
sample = '''(()()()())
(((())))
(()((())()))
((((((())
()))
(()()(()
(()))(
())(()'''
sample = sample.split('\n')
for i in range(len(sample)):
print(f'{sample[i]:20} {isbalpar(sample[i])}')
public static void main(String[] args) {
String balance = new Scanner(System.in).nextLine();
System.out.println(balanceCheck(balance));
}
private static boolean balanceCheck(String balance) {
balance = balance.replaceAll("[^()]", "");
for (int j = 0; j < balance.length() / 2 + 1; j++)
for (int i = 0; i < balance.length() - 2; i++)
if (balance.substring(i).startsWith("()"))
balance = balance.substring(0, i) + balance.substring(i + 2);
return balance.equals("()");
}
import re
def bracket_balance() :
s= input("괄호입력")
s=re.sub("[^\(\)]","",s)
o_cnt=0
c_cnt=0
for i in range(0, len(s)) :
#닫는 괄호가 더 많아지면 false
if o_cnt<c_cnt :
return False
elif s[i]=="(" :
o_cnt+=1
continue
elif s[i]==")" :
c_cnt+=1
continue
if o_cnt==0 and c_cnt==0 :
raise ValueError
return o_cnt==c_cnt
D ='(5+6)∗(7+8)/(4+3)'
count=0
for i in D:
if i =='(': count+=1
elif i ==')': count -=1
if count ==0: print('정상')
else: print('비정상')
간단하게 작성해봤습니당
def bracket(st):
st = list(st)
while len(st) >= 2:
if st[0] == '(':
del st[0]
del st[st.index(')')]
else:
break
return 'TRUE' if st == [] else 'FALSE'
def is_Balanced(a):
alist = list(a)
left = alist.count('(')
right = alist.count(')')
if left == right:
return True
else:
return False
str = input()
print(is_Balanced(str))
while True:
paren=input("Input parenthesis: ")
def checkparen(paren):
if paren.count("(")!=paren.count(")"):
return False
else:
for i in range(len(paren)):
check=paren[:i]
if check.count("(")<check.count(")"):
return False
else:
continue
return True
print(checkparen(paren))
주어진 괄호리스트가 정상적인 괄호 사용이라고 가정하자. 이 때 첫번째 ')'과 바로 왼쪽의 '('을 제거하는 작업을 반복하면 아무것도 남지 않게 된다. 괄호리스트가 비정상적인 괄호 사용이라면 이 작업을 하는 도중 두가지 경우를 마주하게 된다. 첫번째는 괄호리스트가 ')'로 시작되는 경우다. ')'로 시작되는 괄호리스트는 명백한 비정상이기 때문에 바로 False를 반환한다. 두번째는 '('과 ')' 둘 중 어느 한쪽만 남은 경우다. 이 때 리스트의 remove 메소드가 오류 메세지를 보낸다. 여기서 예외처리를 해 False를 반환하면 된다.
def isSBP(s):
L = list(s)
while len(L) != 0:
if L[0] == ')':
return False
else:
try:
L.remove('(')
L.remove(')')
except:
return False
return True
print(isSBP('(()((())()))'))
괄호의 수도 같아야 하고 짝수에, 양 2번째 끝 쪽까지 반대면 참을 반환하는 프로그램 입니다.
def Balanced(Parentheses):
if len(Parentheses) % 2 == 0 and \
Parentheses.count('(') == Parentheses.count(')') and \
Parentheses[0] != Parentheses[-1] and Parentheses[1] != Parentheses[-2 and \
Parentheses[0] == '(':
return True
else:
return False
Parentheses= '(()()()())'
def judd(S):
if S=='':
return 'balanced'
elif S[0]==')' or len(S)%2==1:
return 'not balanced'
elif ')' not in S:
return 'not balanced'
return judd(S.replace('()',''))
rs=input();s=''
for i in rs:
if i!='(' and i!=')':
continue
else:
s+=i
print(judd(s))
처음에 아무 생각없이 괄호의 짝이 잘 맞아가는지 만 판단하는 코드를 짜고 넘어가려 했었는데, 이 문제의 본질은 그것에 있지 않은가 생각이 들읍니다. 문제의 지적에도 있듯이, 만약 )( 같은 문자열이 입력이 된다면은 괄호의 짝은 맞으나 실제로 완전히 잘못된 사용이지요. 그래서 다시 짜보았읍니다. 이런저런 궁리가 있겠으나, 그냥 가장 단순하게 입력된 문자열에서 '( )'를 모두 제거한 상태로 재귀함수를 돌렸읍니다. 물론, 실제에서 숫자나 여러 함수없이 「(」과「)」기호만을 사용한 연산은 없으니, )과 (를 제외한 모든 문자열 역시 튕겨내고내서 재귀에 돌렸읍니다. 굳이 이러한 조작을 하지 않고도 충분히 할 수 있다고 생각이 들지만, 길이가 1억을 넘는 문자열이 아닌 이상 일순한는데에 시간도 굳이 안 들것같고 무엇보다 귀찮아서 그냥 다 지우고 가기로했읍니다.(제가 지금 구현한 코드에서는 안지우고 가나, 지우고 가나, 길이가 비슷해지더군요.)
rs=input();s=''
for i in rs:
if i!='(' and i!=')':
continue
else:
s+=i
while '()' in s:
s=s.replace('()','')
if s=='':
print('balanced')
else:
print('not balanced')
그러나, 굳이 재귀함수를 쓸 필요는 없었읍니다. 최근 재귀함수에 푹 빠져있어서 어느것이든 재귀를 먼저 떠올리고 마는데, 알고리즘을 짜면서 차근차근 정리를 하여보니, 굳이 재귀를 쓰지 않아도 풀 수가 있더군요. 무엇보다 재귀를 쓰지 않고 푸는쪽이 가독성면에서는 더 간단하고 길이도 짧았읍니다. 허나, 평소 어려워하던 재귀를 이렇게까지 굳이 구현 해 냈다는것을 다르게 생각을 해 보면 그만큼 재귀에 익숙해져 있는것이 아닌가 생각도 들읍니다 .^^
a=input("수식입력: ")
b=[]
c=[]
for i in a:
if i=='(':
b.append(i)
elif i==")":
b.append(i)
x=len(b)
print(b)
for j in b:
if j=='(':
c.append(j+')')
if b.count(')'):
b.remove(')')
else:
break
elif j==')':
break
print(c)
print(b)
if c.count("()")==x/2:
print('True')
else:
print('False')
Python 3.7
a = 0
for i in input():
if i == '(':a+=1
elif i == ')':a-=1
if a < 0:break
if a == 0:
print('True')
else:
print('False')
여는 괄호"("와 닫는 괄호")"의 갯수가 항상 일치해야 하고, 닫는 괄호는 여는 괄호보다 먼저 나오면 안됩니다.
따라서 여는 괄호를 +1, 닫는 괄호를 -1로 카운팅해서 중간에 값이 음수가 되면 False, 최종 값이 0이 아니면 False를 출력하도록 했습니다.
python3
def check(str1):
count1 = 0
for s in str1:
if s == '(':
count1 += 1
elif s == ')':
count1 -= 1
if count1 < 0:
print(False)
return False
if count1 == 0:
value = True
else:
value = False
print(value)
return value
data = [
'(()()()())',
'(((())))',
'(()((())()))',
'((((((())',
'()))',
'(()()(()',
'(()))(',
'())(()'
]
result = list(map(check, data))
print(result)
def function(char):
count = 0
if char.count("(") != char.count(")"):
return False
else :
if char[0] !="(" or char[-1] !=")" :
return False
else :
for i in range(len(char)):
if char[i] =="(":
count += 1
elif char[i] == ")":
count -= 1
if count < 0:
return False
if count == 0:
return True
else :
return False
print("Normal")
data = function("(()()()())")
print(data)
data = function("(((())))")
print(data)
data = function("(()((())()))")
print(data)
print("ABnormal")
data = function("((((((())")
print(data)
data = function("()))")
print(data)
data = function("(()()(()")
print(data)
data = function("(()))(")
print(data)
data = function("())(()")
print(data)
public class SimpleBalancedParentheses {
public static void main(String[] args) {
Balance("(()()()())");//balance
Balance("(((())))");//balance
Balance("(()((())()))");//balance
Balance("((((((())");//not balance
Balance("()))");//not balance
Balance("(()()(()");//not balance
Balance("(()))(");//not balance
Balance("())(()");//not balance
}
public static void Balance(String line) {
int count1 = 0;
int count2 = 0;
String[] lines = line.split("");
for(int i=0; i<lines.length; i++) {
if(count1>=count2) {
if(lines[i].equals("(")) {
count1++;
}
else if(lines[i].equals(")")) {
count2++;
}
}
else {
System.out.println("not balanced");
break;
}
if(i==lines.length-1) {
if(count1==count2) {
System.out.println("balanced");
}
else {
System.out.println("not balanced");
}
}
}
}
}
import re
def main(li) :
balancing_com = re.compile("\([^\(^\)]*\)")
while True :
try :
det = balancing_com.search(li).group()
li = balancing_com.sub(det[1:-1], li)
except :
if li == '' : return True
else : return False
return li
if __name__ == '__main__' :
print(main(input("INPUT : ")))
정규식을 활용해봤습니다.
결과
INPUT : (()()()())
True
INPUT : ((((((())
False
INPUT : (()((())()))
True
INPUT : (()()(()
False
a=input('괄호 사용된 문자 : ')
op=0
cl=0
for i in range(len(a)):
if a[i]=='(':
op+=1
elif a[i]==')':
cl+=1
if op==cl:
print('True')
if a[0]==')':
print('False')
else:
print('False')
N = input()
openclosecheck = 0
opencheck = list()
check = 0
for i in range(len(N)):
if N[i] == '(':
openclosecheck += 1
opencheck.append(1)
if N[i] == ')':
openclosecheck -= 1
if len(opencheck) == 0 == 0:
print("not balanced")
check = 1
break
else:
opencheck.pop(0)
if openclosecheck != 0 and check == 0:
print("not balanced")
if openclosecheck == 0 and check == 0:
print("balanced")
a=str(input('input......'))
n,i=0,0
while (i<len(a)):
if a[i]=='(':
n+=1
elif a[i]==')':
n-=1
if n<0:
break
i+=1
if n==0:
print('Balanced')
else:
print('Not Balanced')
def sbp(p, n):
for i in range(len(p)):
n += (1 if p[i] == '(' else -1)
if n < 0:
return 'Not balanced'
return 'Balanced' if n == 0 else 'Not balanced'
def main():
p = '(()((())()))'
print(sbp(list(p), 0))
if __name__ == '__main__':
main()
def check_parentheses(s):
count = 0
for i in s:
if i == "(":
count += 1
if i == ")":
count -= 1
if count < 0:
return False
return count == 0
def balance(s):
depth=0
for c in s:
if c=='(':
depth+=1
if c==')':
depth-=1
if depth < 0 :
return False
if depth == 0:
return True
else:
return False
inp=input("괄호를 입력하십시오: ")
mn=len(list(inp))
n=1
while n<=mn:
inp=inp.split("()")
if inp==[""]:
print("True")
break
inp="".join(inp)
n+=1
if inp!=[""]:
print("False")
결과
(()()()()) #True
(((()))) #True
(()((())())) #True
((((((()) #False
())) #False
(()()(() #False
(()))( #False
())(() #False
package test;
import java.util.*;
public class Test{
public static void main(String[] args) {
int count = 0;
Scanner sc = new Scanner(System.in);
String input = sc.nextLine();
char[] arr = input.toCharArray();
for(int i = 0; i < arr.length; i++) {
if(arr[i] == '(')
count++;
else if(arr[i] == ')')
count--;
}
if(count !=0)
System.out.println("not balanced");
else if(count == 0)
System.out.println("balanced");
sc.close();
}
}
def blanced(s):
result = True if s.count('(') == s.count(')') else False
if s[-1] == '(': result = False
for i in range(0, len(s)-1):
if s[:i].count('(') == s[:i].count(')') and s[i+1] == ')':
result = False
break
print(result)
def Simple_Balanced(strings):
for_answer=[]
for i in range(0,len(strings),1):
if strings[i] == '(':
for_answer.append('(')
elif len(for_answer)==0:
return "unbalanced"
break
else:
for_answer.pop()
if for_answer==[]:
return "balanced"
else:
return 'unbalanced'
def main(a):
print(Simple_Balanced(a))
main('((((()))')
main('()))')
main("(((())))")
def balanced(text):
_open = 0
_error = 0
temp = []
for aa in text:
if aa == '(':
temp.append(0)
_open += 1
# print(aa, _open, temp)
elif aa == ')':
if 0 not in temp:
_error = 1
# print('ERROR')
break
else:
for i in range(len(temp)):
if temp[len(temp)-i-1] == 0:
temp[len(temp)-i-1] = 1
_open = _open - 1
# print(aa, _open, temp)
break
if _open == 0 and _error == 0:
print("TRUE")
return True
else:
print("FALSE")
return False
balanced('(()()()())')
balanced('(((())))')
balanced('(()((())()))')
balanced('((((((())')
balanced('()))')
balanced('(()()(()')
balanced('(()))(')
balanced('())(()')
def count(bal):
count = 0
for b in bal:
if count >= 0:
if b == '(':
count += 1
elif b == ')':
count -= 1
if count == 0:
print('정상')
else:
print("비정상")
a = "(((()))((((((((())))))))))"
b = list(a)
q=0
cnt =1
if len(a)/2 == b.count(')') and a[0] != a[-1]:
for i in range(1,len(a)-2):
if b[i]!=b[-i-1] and b[1]=='(':
#print("true")
break
elif b[i]!=b[i+1]:
cnt-=1
elif b[i]==b[i+1]:
cnt+=1
q+=i
if abs(cnt)%2==1 or q==0 or cnt==0:
print("True")
else:
print("false")
else:
print("False")
잘푸신분들은 어떻게 저런생각을하지..
def nice(a):
return ('False','True')[a.count('(') == a.count(')')]
print(nice('(()()()())'))
print(nice('((((((())'))
#codingdojing_Simple Balanced Parentheses
'''
1. 왼쪽부터 차례대로 읽어서, (개수와 )개수를 센다.
2. 언제나 (의 개수가 )보다 더 많아야해. '''
def SBP(sentence):
if sentence.count('(') != sentence.count(')'):
return False
p_dic = {'(' : 0, ')' : 0}
for s in sentence:
p_dic.setdefault(s, 0)
p_dic[s] += 1
if p_dic['('] < p_dic[')']:
return False
return True
sentence = '(5+6)∗(7+8)/(4+3)'
print(SBP(sentence))
def SimpleBalancedParentheses(a,x = False):
cnt = 0
for i in a:
if i == '(':
cnt += 1
else:
cnt = cnt -1
if cnt < 0:
return x
elif cnt == 0:
return True
else:
return cnt == 0
if __name__ == '__main__':
a = input()
print(SimpleBalancedParentheses(a))
a = input()
if a.count("(")==a.count(")") and a[0]=="(" and a[-1]==")" \
and a[:int(len(a)/2)].count("(") >= a[:int(len(a)/2)].count(")"):
print("정상")
else :
print("비정상")
문자열로 받아서 몇가지 규칙만 적용 해보니 간단히 해결되는거 같아요 혹시 허점이 있으면 댓글 부탁드려요
a= '(()()(()'
if a.count('(') == a.count(')'):
print('balanced case')
else:
print('not balanced case')
def SBP(S):
count = 0
for i in S:
if i == '(':
count += 1
elif i == ')':
count -= 1
if count < 0:
return print('비정상')
if count == 0:
return print('정상')
else:
return print('비정상')
SBP('(()()()())')
SBP('((((((())')
def checkPalentheses(palens):
ap = []
for p in palens:
if p=='(':
ap.append(p)
elif len(ap)>0:
ap.pop()
else:
return False
return True if len(ap)==0 else False
print(checkPalentheses('(()()()())'))
print(checkPalentheses('(((())))'))
print(checkPalentheses('(()((())()))'))
print(checkPalentheses('((((((())'))
print(checkPalentheses('()))'))
print(checkPalentheses('(()()(()'))
print(checkPalentheses('(()))('))
JAVA입니다. 비정상적인 괄호가 되는 경우에는 두 가지가 있는데, 첫 번째는 왼쪽, 오른쪽 괄호 수의 총합이 맞지 않는 것이고 두 번째는 오른쪽 괄호와 짝을 이루는 왼쪽 괄호를 그 오른쪽 괄호 이전에서 찾을 수 없는 경우입니다.("(()))("같은 경우) 두 번째 경우를 판별하기 위해서 문자열의 매 문자마다 왼쪽 괄호 수가 오른쪽 괄호 수보다 크거나 같은지를 확인했습니다.
package Simple_Balanced_Parenthesis;
public class Parenthesis {
public static void main(String[] args) {
// TODO Auto-generated method stub
String input = "(()))(";
System.out.println(isCorrect(input));
}
public static boolean isCorrect(String input) {
char[] parentheses = input.toCharArray();
int left = 0;
int right = 0;
for (char c : parentheses) {
if (c == '(') {
left++;
}
else if (c == ')') {
right++;
}
if(left < right) {
return false;
}
}
return left == right;
}
}