如果正解是 O(N), 那應該還是要用 stack 來做,
我是除了原本的 x 外, 又多兩種變數 y、z,
其中 y 是外面有一層括號, 但還不確定要不要拿掉,
像 (x) 就會變成 y,
而 z 是相乘之後得來的, 基本上不能再分解,
接下來把所有東西一一丟進 stack 裡, (註:我是直接把 + 丟掉)
遇到右括號 ) 再從 stack 裡一一拿出來直到遇到左括號 ( 為止,
然後把中間的東西轉換成 y 或 z 其中一個,
規則如下:
1.如果 ( ) 裡只有一個東西, (x) 會變成 y 再丟回去,
(y)、(z) 則外面的括號可以去掉。
2.當 y、z 被丟回 stack 時, 如果頂端是 *,
不管是 y*y、y*z、z*y、z*z 都會變成 z。
3.如果 ( ) 裡有兩個以上的東西, 則裡面所有的 y 的括號都可以去掉,
而整個內容最後也會變成 y。
4.最後, 如果 stack 最後只剩下一個 y, 則可以再去掉一個 ( )
5.因為最後的 ( ) 一定要留下, 所以把去掉的 ( ) 數減一就是答案。
基本上應該是這樣, 不知道還有沒有沒考慮到的地方。
參考程式:(By sagit)
#include <cstdlib>
#include <iostream>
using namespace std;
char Stack[200], *p;
int top, cnt;
void Push(char c)
{
if (c>='x'&&c<='z'&&top>=2&&Stack[top]=='*')
{
top-=2;
Push('z');
}
else Stack[++top]=c;
}
int main()
{
int t, i;
char s[200], c;
cin >> t;
cin.getline(s, 200);
while (t--)
{
cin.getline(s, 200);
for (p=s; *p; p++)
if (*p==')') break;
for (p+=2, top=-1, cnt=0; *p; p++)
{
c=*p;
switch (c)
{
case '(':
case 'x':
case '*':
Push(c);
break;
case ')':
if (Stack[top-1]=='(')
{
switch(Stack[top])
{
case 'x':
top-=2;
Push('y');
break;
case 'y':
top-=2;
cnt++;
Push('y');
break;
case 'z':
top-=2;
cnt++;
Push('z');
break;
}
}
else
{
for (i=top; Stack[i]!='('; i--)
if (Stack[i]=='y') cnt++;
top=i-1;
Push('y');
}
break;
}
}
if (top==0&&Stack[0]=='y') cnt++;
cout << cnt-1 << endl;
}
return 0;
}