高中生程式解題: b838: 104北二2.括號問題－資工趴趴熊的小天地

Content

2．括號問題 (104北二區桃竹苗 )

問題描述

小明要解決一大堆的數字加減乘除運算，好在小明有一個好用的電腦程式，只要輸入問題，程式即輸出答案。例如小明輸入 3×((3+5)×4-(2×2))，程式輸出84。但是，這個程式只能用來計算「正確」的輸入，也就是式子中的括號必須成對而且先出現左括號再出現右括號。請你寫一個程式判斷一個式子中的括號是否正確，若正確的話，請輸出式子中有幾對括號，若錯誤的話，請輸出0。

Input

第1列有一正整數t(<1000)表示有t組資料，接著t列，代表一個式子。為了簡化問題，式子中的數字與加、減、乘、除等運算元皆已移除，只留下括號，中間沒有空白。每筆輸入的括號符號數最多20 個。

Output

根據每列資料，輸出式子中的括號是否正確（成對且先出現左括號再出現右括號）。若正確的話，請輸出式子中有幾對括號，若不正確請輸出0。

Sample Input #1

2
(()()) 
((()())

Sample Output #1

3
0

C++

#include <iostream>
#include <stack>
using namespace std;
/*
使用stack，只有正確規則下才pop(同時計數器+1)，否則都一直push， 
最後檢查 stack若有東西，代表括弧不對，輸出0 
*/
int main(){
	int n;
	string s;
	stack<int> stk;
	cin>>n;
	while(n--){
		cin>>s;
		int count=0;
		for(int i=0;i<s.length();i++){
			//cout<<s[i]<<' ';
			if(!stk.empty() && stk.top()=='(' && s[i]==')'){//有條件才pop 
				//cout<<"pop"<<' '; 
				stk.pop();
				count++;
				//cout<<count<<'\n';
			} 
			else{
				//cout<<"push"<<' '; 
				stk.push(s[i]);
			}
		}
		if(!stk.empty()){
			count=0;
		}
		cout<<count<<'\n';
	}
	return 0;
}

python:

#解題方式沒錯，但側資一會過不了
n=int(input())
for _ in range(n):
    arr=input()[::1]
    #print(arr)
    new=[]
    ans=0
    for i in range(len(arr)):
        if(len(new)>0 and new[-1]=="(" and arr[i]==")"):
            new.pop()
            ans+=1
        else:
            new.append(arr[i])
        #print(new)
    if(len(new)>0):
        ans=0
    print(ans)