a229: 括號匹配問題
#-*- coding: utf-8 -*
'''
#除了要加上# -*- coding: utf-8 -*-外，中文字串必須是Unicode字串：
請寫一個程式把所有合法括號匹配方式列出來!
Ex. (()) , ((()())) , ()((())) 是合法的匹配方式
)( , (()))( , ()(()( 是不合法的匹配方式
合法匹配的括號 ， 從答案列的開頭到答案列某一點，左括弧次數永遠大於等於右括弧!
輸入說明
輸入一個正整數 N ， 1 =< N <= 13 。
N 代表有幾組括號要匹配
Ex.
N = 1 代表 一組括號 ()
N = 2 代表有兩組括號 ()()
輸出說明
輸出 N 組括號的所有合法匹配組合
輸出方式請見範例
範例輸入 #1
1
2
3
4
範例輸出 #1
()
(())
()()
((()))
(()())
(())()
()(())
()()()
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()
'''
num=0
def pa(le , ri , n):
if (n==2*num) : # {//終止遞迴
for i in range (0 , 2*num):
print(qu[i],end='')
print("\n")
return;
if (le<num): # {//le表示已經加入的左小括號個數，從0開始不能超過或等於num
qu.append('(')
pa(le+1,ri,n+1) #//多了一個左小括號le+1，n+1為已經加入的左與右小括號個數
qu.pop()
if ((le>ri) and (ri<num)): #//左小括號要大於右小括號數，且右小括號數要小於num
qu.append(')')
pa(le,ri+1,n+1) #//多了一個右小括號ri+1，n+1為已經加入的左與右小括號個數
qu.pop()
#=======================
from collections import deque
qu = deque()
#deque一個類似 list 的容器，可以快速的在頭尾加入 (append) 元素與移除 (pop) 元素
while True:
n = (input('\n一個正整數n， (EOF 為結束) -->'))
if n == '':
print('程式結束')
break
num=int(n)
pa(0,0,0);
'''
# Python program to
# demonstrate stack implementation
# using collections.deque
from collections import deque
stack = deque()
# append() function to push
# element in the stack
stack.append('a')
stack.append('b')
stack.append('c')
print('Initial stack:')
print(stack)
# pop() function to pop
# element from stack in
# LIFO order
print('\nElements popped from stack:')
print(stack.pop())
print(stack.pop())
print(stack.pop())
print('\nStack after elements are popped:')
print(stack)
# uncommenting print(stack.pop())
# will cause an IndexError
# as the stack is now empty
Output
Initial stack:
deque(['a', 'b', 'c'])
Elements popped from stack:
c
b
a
Stack after elements are popped:
deque([])
'''
Python 3.7.9 (bundled)
>>> %Run a229.py
一個正整數n， (EOF 為結束) -->1
()
一個正整數n， (EOF 為結束) -->2
(())
()()
一個正整數n， (EOF 為結束) -->3
((()))
(()())
(())()
()(())
()()()
一個正整數n， (EOF 為結束) -->4
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()
一個正整數n， (EOF 為結束) -->5
((((()))))
(((()())))
(((())()))
(((()))())
(((())))()
((()(())))
((()()()))
((()())())
((()()))()
((())(()))
((())()())
((())())()
((()))(())
((()))()()
(()((())))
(()(()()))
(()(())())
(()(()))()
(()()(()))
(()()()())
(()()())()
(()())(())
(()())()()
(())((()))
(())(()())
(())(())()
(())()(())
(())()()()
()(((())))
()((()()))
()((())())
()((()))()
()(()(()))
()(()()())
()(()())()
()(())(())
()(())()()
()()((()))
()()(()())
()()(())()
()()()(())
()()()()()
一個正整數n， (EOF 為結束) -->
程式結束
>>>
沒有留言:
張貼留言