魔王语言集锦
魔王语言集锦
问题描述：
设计并实现魔王语言的解释器，具体要求如下：大写字母表示魔王语言的词汇；小写字母表示人的词汇语言；魔王语言中可包含括号。
如：我们有魔王语言的解释规则：B－>tAdA；A->sae；则魔王语言 B(ehnxgz)B解释成tsaedsaeezegexenehetsaedsae。
我的解决：
/**********************************************************************
* *
* File name: FiendLanguage.cpp *
* Function: A simple Cpp expriment *
* Platform: Win Xp SP2 *
* Compiler & Linker: CL.exe 8.0 (in Visual Studio 2005 SDK) *
* Programmer: 88250 *
* Complete date: September 15, 2006 Version: 1.0 *
* Note: Can't solve nesting of parentheses! *
* The resolution will appear in Ver 2.0 :-) *
* Blog: http://DL88250.ynutx.net *
* E-mail: DL88250@gmail.com *
* QQ: 845765 or 316281008 *
* *
**********************************************************************/
＃i nclude <stack>
＃i nclude <queue>
＃i nclude <string>
＃i nclude <iostream>
using namespace std;
int main(int argc, char *argv[])
{
char theta, tmp;
queue<char>q;
stack<char> f, h;
string A = "sae";
string BA = "tsaedsae";
string fiendLang = "B(ehxBgzA)B";
string humanLang;
//cout << "Fiend says: ";
//cin >> fiendLang;
// push fiend's language into stack
for (int i = 0; i < fiendLang.length(); i++)
{
f.push(fiendLang.at(i));
}
while (!f.empty())
{
tmp = f.top(), f.pop(); // tmp may be 'A', 'B' or ')'
if (tmp == 'A')
{
for (int i = A.size() - 1; i >= 0; i--)
{
h.push(A.at(i));
}
}
else if (tmp == 'B')
{
for (int i = BA.size() - 1; i >= 0; i--)
{
h.push(BA.at(i));
}
}
else if (tmp == ')')
{
while (f.top() != '(')
{
q.push(f.top());
theta = f.top(); // overriding theta
f.pop();
}
while (!q.empty())
{
f.push(q.front()), q.pop();
}
f.pop(); // pop a theta
h.push(theta);
while (f.top() != '(')
{
if (f.top() == 'A')
{
for (int i = A.size() - 1; i >= 0; i--)
{
h.push(A.at(i));
}
}
else if (f.top() == 'B')
{
for (int i = BA.size() - 1; i >= 0; i--)
{
h.push(BA.at(i));
}
}
else
{
h.push(f.top());;
}
h.push(theta);
f.pop();
}
f.pop(); // pop '('
}
}
humanLang.erase();
while (!h.empty())
{
humanLang.append(1, h.top());
h.pop();
}
cout << humanLang;
return 0;
}
这个是版本1.。。。不能解决括号的嵌套问题。。。。
下面这个是升级版啦:-P
/**********************************************************************
* *
* File name: FiendLanguage.cpp *
* Function: A simple Cpp expriment----Fiend's Language *
* Platform: Win Xp SP2 *
* Compiler & Linker: CL.exe 8.0 (in Visual Studio 2005 SDK) *
* Programmer: 88250 *
* Complete date: September 20, 2006 Version: 2.0 *
* Blog: http://DL88250.ynutx.net *
* E-mail: DL88250@gmail.com *
* QQ: 845765 or 316281008 *
* *
**********************************************************************/
＃i nclude <stack>
＃i nclude <queue>
＃i nclude <string>
＃i nclude <iostream>
using namespace std;
string A = "sae";
string BA = "tsaedsae";
string tmpStr[10]; // interpreted language in parenthese
unsigned int n = 0; // the subscription of tmpStr[]
// if transformed one sentances in the parentheses
// the parenFlag equal to true, flase otherwise
bool parenFlag;
string fiendLangFrontPar = "B";
string fiendLangRearPar = "B";
string fiendLangInPar = "(aAbA(cd)e(f(gh)A))";
string humanLang; // save interpreted language
/*******************************************************************
* Func: transform one sentance in the parentheses to intermediate
* language
* Argvs: one sentance in the parentheses
* Ret: void
*******************************************************************/
void transform(string inParentheses)
{
stack<char> f, h;
queue<char> q;
char theta;
// push fiend's language into stack
for (int i = 0; i < inParentheses.size(); i++)
{
f.push(inParentheses.at(i));
}
while (!f.empty())
{
q.push(f.top());
theta = f.top(); // overriding theta
f.pop();
}
while (!q.empty())
{
f.push(q.front()), q.pop();
}
f.pop(); // pop a theta
h.push(theta);
while (!f.empty())
{
h.push(f.top()), f.pop();
h.push(theta);
}
inParentheses.erase();
while (!h.empty())
{
inParentheses.append(1, h.top());
h.pop();
}
tmpStr[++n].append(inParentheses);
return;
}
/*****************************************************
* Func: resolve nesting parentheses problem
* Argvs: sentance in the parentheses
* Ret: boolean type, confirm whether transformed
* one sentance in the parentheses. if accomplish one
* transformation return true, flase otherwise
*****************************************************/
bool resolve(string &inParentheses)
{
string copyRest;
for (int i = 1; i <= inParentheses.length(); i++)
{
if (inParentheses.at(i) == '(')
{ // get start recursive
parenFlag = resolve(inParentheses.substr(i));
}
if (inParentheses.at(i) == ')')
{ // return from a recursive
transform(inParentheses.substr(1, i-1));
return true;
}
if (true == parenFlag)
{ // use n to replace the content which in the parentheses
copyRest.assign(inParentheses.substr(inParentheses.find(')')+1));
inParentheses.insert(i, 1, n);
inParentheses.replace(i+1, copyRest.length(), copyRest);
parenFlag = false;
}
}
}
/*****************************************************************
* Func: interpret sentances out of the outerest parentheses
* Argv: sentance out of the outerest parentheses
* Ret: void
*****************************************************************/
void generInterpreter(string outLang)
{
for (int i = 0; i < outLang.length(); i++)
{
if ('A' == outLang.at(i))
{
humanLang.append(A);
}
else
{
humanLang.append(BA);
}
}
return;
}
/******************************************************************
* Func: interpret sentances in the parentheses
* Argv: intermediate language string, like: a3aea1ab
* Ret: void
******************************************************************/
void parInterpreter(string myLang)
{
for (int i = 0; i < myLang.length(); i++)
{
if (isalpha(myLang.at(i))) // is a character ?
{
if ('A' == myLang.at(i))
{
humanLang.append(A);
}
else if ('B' == myLang.at(i))
{
humanLang.append(BA);
}
else
{
humanLang.append(1, myLang.at(i)); // interpreter complete
}
}
else
{ // recursive
parInterpreter(tmpStr[myLang.at(i)]); // into tmpStr[n]
}
}
return;
}
// program entry
int main(int argc, char *argv[])
{
string fiendLang;
cout << "Fiend says: ";
cin >> fiendLang;
// clean the original data
fiendLangFrontPar.erase();
fiendLangRearPar.erase();
fiendLangInPar.erase();
// separate the original Fiend's language into 3 parts
// for example, the original data is:
// ABA(BaAbA(cd)e(f(gh)A))BA
// now, we separate it like this:
// fiendLangFrontPar = "ABA"
// fiendLangInPar = "(BaAbA(cd)e(f(gh)A))"
// fiendLangRearPar = "BA"
// part fiendLangFrontPar from fiendLang
for (int i = 0; i < fiendLang.length(); i++)
{
if ('(' == fiendLang.at(i))
{
break;
}
else
{
fiendLangFrontPar.append(1, fiendLang.at(i));
fiendLang.erase(i, 1);
i--; // replace i
}
}
// part fiendLangRearPar from fiendLang
for (int i = fiendLang.length() - 1; i >= 0; i--)
{
if (')' == fiendLang.at(i))
{
break;
}
else
{
fiendLangRearPar.append(1, fiendLang.at(i));
fiendLang.erase(i, 1);
}
}
// part fiendLangInPar from fiendLang
fiendLangInPar.assign(fiendLang);
// interpret the fiendLangFrontPar part
generInterpreter(fiendLangFrontPar);
// transform the fiednLangInPar part into
// intermediate language
tmpStr[n].assign(fiendLangInPar);
resolve(tmpStr[n]);
// interpret the fiendLangInPar part
parInterpreter(tmpStr[n]);
// interpret the fiendLangRearPar part
generInterpreter(fiendLangRearPar);
// ouput the final result
cout << humanLang;
return 0;
}
Ver1.0比较简单，就不说了。说说对Ver2.0的分析：
用了动态规划+递归：
先弄个string tmp[10]来保存中间结果，现在假设要解释的串是：
(ab(cd)e(f(hg)))->tmp[0] ->表示保存到的意思
首先进入第一个括号，S1:ab。现在遇到一个括号，递归：
S2:cd经过transform->tmp[1]返回到S1,并保存1到ab后。下一个遇到e，不管，继续。遇到括号，进入：
S3：f，又遇到括号，进入：
S4：hg经过transform->tmp[2],返回S3,现在S3里是f2,现在transform->tmp[3]返回到S1,现在S1是ab1e3，现在可以transform S1->tmp[4]！
中间的结果如下：
tmp[1]:cdc
tmp[2]:hgh
tmp[3]:f2f
tmp[4]:a3aea1aba
最后对tmp[4]进行递归解释得：afhghfaeacdcaba
这就是整个过程的描述了。。。。