怎么判断出栈序列的合法性

如何判断出栈序列的合法性?
bool test(char* str1, char*str2);

判断出 str2 是str1 的合法出栈序列。

测试用例：
str1 = "abcb"; str2 = "cbab"; 返回ture. 



[解决办法]
提示（用递归）：考虑最后出栈的元素，它进栈是，栈应该是空的。
[解决办法]

C/C++ code

#include <stack>#include <iostream>using std::stack;using std::cout;using std::endl;/*判断str2是否为str1的合法出栈序列*/bool isLegalSequence(char const *str1, char const *str2) {    stack<char> stk;    while (*str1 && *str2)    {        if (stk.empty())         {            stk.push(*str1++);        }        if (stk.top() != *str2)        {            stk.push(*str1++);        }         else         {            stk.pop();            ++str2;        }    }    return stk.empty() ? true : false;}void main(){    cout << (isLegalSequence("abcbd", "xxxxx") ? "Yes" : "No") << endl;}
[解决办法]
从左往右扫描，只要做到出栈优先就可以了。
因为出栈优先一定可以转换成入栈优先状态，反过来就不一定了。
[解决办法]
C/C++ code
#include<iostream>#include<stack>using namespace std;bool judge(const char *push_seq, const char *pop_seq){    if (NULL == push_seq || NULL == pop_seq)    {        return false;             }    if (strlen(push_seq) != strlen(pop_seq))    {        return false;    }        stack<char>sc;    while (*push_seq)    {        if (0 == sc.size() || sc.top() != *pop_seq)        {            sc.push(*push_seq++);        }        else        {            sc.pop();            ++pop_seq;        }    }        while (sc.size())    {        if (sc.top() != *pop_seq++)        {            return false;        }        sc.pop();    }        return true;}int main(){    cout<<judge("abcb", "cbab")<<endl;    system("pause");    return 0;}
[解决办法]

  i<j<k 且 Sk>Si>Sj,
S表示出的顺序，i,j,k入序号