時間限制：1 秒
記憶體限制：32 兆
特殊判題：否
送出：5193
解決：2248
- 題目描述：
- 在某個字元串（長度不超過100）中有左括号、右括号和大小寫字母；規定（與常見的算數式子一樣）任何一個左括号都從内到外與在它右邊且距離最近的右括号比對。寫一個程式，找到無法比對的左括号和右括号，輸出原來字元串，并在下一行标出不能比對的括号。不能比對的左括号用"$"标注,不能比對的右括号用"?"标注.
- 輸入：
-
輸入包括多組資料，每組資料一行，包含一個字元串，隻包含左右括号和大小寫字母，字元串長度不超過100。
注意：cin.getline(str,100)最多隻能輸入99個字元！
- 輸出：
- 對每組輸出資料，輸出兩行，第一行包含原始輸入字元，第二行由"$","?"和空格組成，"$"和"?"表示與之對應的左括号和右括号不能比對。
- 樣例輸入：
-
)(rttyy())sss)(
- 樣例輸出：
-
)(rttyy())sss)( ? ?$
- 來源：
- 2010年北京大學計算機研究所學生機試真題
思路：
簡單的DP，也可以說貪心。累計左括号值，遇到右括号則減一，如果左括号值為0時碰到右括号則不比對。而且最後的幾個左括号也不比對。
用堆棧存儲左括号位置，不用堆棧其實行。
代碼：
#include <stdio.h>
#define M 100
int stack[M];
int top;
int push(int x)
{
if (top == M)
return 0;
stack[top] = x;
top ++;
return 1;
}
int pop(int *x)
{
if (top == 0)
return 0;
top --;
*x = stack[top];
return 1;
}
int main(void)
{
int x, i;
char s[M+1], s2[M+1];
while (scanf("%s", s) != EOF)
{
top = 0;
for(i=0; s[i]; i++)
{
if (s[i] == '(')
{
push(i);
s2[i] = ' ';
}
else if (s[i] == ')')
{
if ( !pop(&x) )
s2[i] = '?';
else
s2[i] = ' ';
}
else
s2[i] = ' ';
}
s2[i] = '';
while (top)
{
pop(&x);
s2[x] = '$';
}
printf("%s
", s);
printf("%s
", s2);
}
return 0;
}
/**************************************************************
Problem: 1153
User: liangrx06
Language: C
Result: Accepted
Time:0 ms
Memory:912 kb
****************************************************************/