上篇博客文章《简易逻辑表达式词法分析器》讲到设计了一个逻辑表达式词法分析器,这次以那个词法分析器作为后端,利用VC搭建前端界面,展示一下分析效果。
分析结果以树的形式表示:同一级节点表示具有相同的等级,参数比它的谓词的等级要高,比如Missile(x)中Missile等级为0级,x为1级。分析之后各个节点存储在Parser.list中,可以根据该链表的节点的level属性将各节点插入树种的相应位置。
分析以上逻辑表达式可知,各个节点的等级如下:
Missile x AND Owns Nono Sub x => Sells West x Nono
0 1 0 0 1 1 2 0 0 1 1 1
可见,利用堆栈来辅助将节点插入树中是最理想的方法。思路如下:将树的TVI_ROOT压栈;若当前节点的等级大于其前一个节点,将前一个节点压栈;若当前节点等级小于前一个节点,出栈前一节点等级 和 当前节点等级之差次;若当前节点等级等于前一节点等级,既不压栈也不出栈。每个当前节点的父节点为栈顶元素。
源代码如下:
void CPPageFaultLogicExpression::OnBnClickedButtonParse()
{
// TODO: 在此添加控件通知处理程序代码
UpdateData(TRUE);
if(m_strLogicExpression==L"")
{
MessageBox(L"请输入逻辑表达式!");
}
else
{
m_parser.Parse((wstring)m_strLogicExpression); // 进行词法分析
m_bIsParsed=TRUE;
//// 向词法分析树种添加分析结果 ////
m_tLexer.DeleteAllItems(); // 清除所有节点
NodeList_It it=m_parser.list.begin();
NodeList_It tmp_it=it;
wchar_t tmp[128];
wcscpy(tmp,it->content.c_str());
stack<HTREEITEM> st; // 定义堆栈
TVINSERTSTRUCT tvInsert;
tvInsert.hParent = TVI_ROOT;
tvInsert.hInsertAfter = TVI_LAST;
tvInsert.item.mask = TVIF_TEXT;
tvInsert.item.pszText = tmp;
HTREEITEM hcur=TVI_ROOT;
st.push(hcur);
hcur=m_tLexer.InsertItem(&tvInsert); // 插入根节点
HTREEITEM hprev;
hprev=hcur;
// int level=0,max_level=0;
it++;
for(it;it!=m_parser.list.end();it++)
{
wcscpy(tmp,it->content.c_str());
if(it->level > tmp_it->level) // 当前节点深度大于前一节点时,前一节点所在的树的位置入栈
{
st.push(hprev);
hcur=m_tLexer.InsertItem(tmp,hprev,TVI_LAST); // 插入新的节点
}
else if(it->level < tmp_it->level) // 当前节点深度小于前一节点时,根据两节点深度之差将保存的节点出栈
{
int level=tmp_it->level;
while(it->level < level--)
{
st.pop();
}
hprev=st.top();
hcur=m_tLexer.InsertItem(tmp,hprev,TVI_LAST); // 插入新的节点
}
else if(it->level == tmp_it->level) // 当前节点深度等于前一节点时,根据栈顶元素插入新节点
{
hprev=st.top();
hcur=m_tLexer.InsertItem(tmp,hprev,TVI_LAST);
}
hprev=hcur;
tmp_it=it;
}
UpdateData(FALSE);
}// end of else
}
{
// TODO: 在此添加控件通知处理程序代码
UpdateData(TRUE);
if(m_strLogicExpression==L"")
{
MessageBox(L"请输入逻辑表达式!");
}
else
{
m_parser.Parse((wstring)m_strLogicExpression); // 进行词法分析
m_bIsParsed=TRUE;
//// 向词法分析树种添加分析结果 ////
m_tLexer.DeleteAllItems(); // 清除所有节点
NodeList_It it=m_parser.list.begin();
NodeList_It tmp_it=it;
wchar_t tmp[128];
wcscpy(tmp,it->content.c_str());
stack<HTREEITEM> st; // 定义堆栈
TVINSERTSTRUCT tvInsert;
tvInsert.hParent = TVI_ROOT;
tvInsert.hInsertAfter = TVI_LAST;
tvInsert.item.mask = TVIF_TEXT;
tvInsert.item.pszText = tmp;
HTREEITEM hcur=TVI_ROOT;
st.push(hcur);
hcur=m_tLexer.InsertItem(&tvInsert); // 插入根节点
HTREEITEM hprev;
hprev=hcur;
// int level=0,max_level=0;
it++;
for(it;it!=m_parser.list.end();it++)
{
wcscpy(tmp,it->content.c_str());
if(it->level > tmp_it->level) // 当前节点深度大于前一节点时,前一节点所在的树的位置入栈
{
st.push(hprev);
hcur=m_tLexer.InsertItem(tmp,hprev,TVI_LAST); // 插入新的节点
}
else if(it->level < tmp_it->level) // 当前节点深度小于前一节点时,根据两节点深度之差将保存的节点出栈
{
int level=tmp_it->level;
while(it->level < level--)
{
st.pop();
}
hprev=st.top();
hcur=m_tLexer.InsertItem(tmp,hprev,TVI_LAST); // 插入新的节点
}
else if(it->level == tmp_it->level) // 当前节点深度等于前一节点时,根据栈顶元素插入新节点
{
hprev=st.top();
hcur=m_tLexer.InsertItem(tmp,hprev,TVI_LAST);
}
hprev=hcur;
tmp_it=it;
}
UpdateData(FALSE);
}// end of else
}
PS1: 当初考虑到中文的支持,利用wstring定义节点内容,现在发现是个错误,在字符转换的过程中很是麻烦,耽误了不少时间,走了不少弯路。
PS2: 也许因为我对STL不是很熟悉,感觉比较麻烦,不知道如何被C++标准委员会接纳的?