摘要：
本程序是一個完整的後綴表達式計算，主要用棧的操作實現，本程序封裝了CStack類實現棧的操作，本程序最大的特色在於運用動態監視表達式的算法對表達式進行數據校驗，對一切合法的表達式進行計算，檢驗出所有任何非法表達式並提示。
關鍵字：後綴表達式，校驗
題目：後綴表達式求值。
要求：輸入後綴表達式，輸入為整數和四則運算，輸出計算結果。
例如：
輸入：2 3 * 1 -
輸出：5
分析：2*3-1=5
輸入：1 2 + 5 4 * 3 - * 6 -
輸出：45
分析：（1+2）*（5*4-3）-6=45
算法分析：
後綴表達式相對於普通的表達式來說，起優點在於不需要括號。所以方便的計算機的處理，通常對於後綴表達式才用棧的數據結果來實現，從左往右掃描表達式，如果遇到的是數字，則把數字壓入棧中；若遇到的是運算符號，則提取棧的的2個元素進行計算，講計算結果壓棧，若最後棧內只剩下一個數字，這就是後綴表達式的計算結果。在此基礎上，考慮到對後綴表達式的校驗，根據後綴表達式計算的特性，編寫了一些函數，對後綴表達式進行校驗，應該可以對任何錯誤的後綴表達式都能校驗出來並提示出錯，在程序中設置了一些狀態，一旦出現了錯誤狀態，立刻停止計算過程，立即報錯。
總體設計：
編程環境是VC6.0，新建MFC工程，選擇為對話框方式，由於表達式是通過一個文本框輸入的，所以在程序中，一定有一個全局函數把字符數字轉化為整型的數字。最主要的那個函數也就是計算那個函數，具體詳細見下面的OnCalculate()函數或者源代碼。本程序采用了棧的數據結構，所以自定義一個CStack類，類的定義，以及實現部分代碼可以見下面代碼。為了完成校驗，另外寫了一個Function.h，在裡面定義了check函數，檢驗輸入表達式是否含有非法數據，trimblank函數，去除表達式中多余的空格，getop函數，取得表達式中運算符號的個數，具體見源代碼。在主函數中，檢驗的思想是首先判斷表達式中時候含有非法字符，若沒有，則進一步判斷表達式中的的數字個數與符號個數時候否滿足“數字個數-1=符號個數”，若滿足，則在計算過程中監測在遇到運算符號的時候時候會出現棧內元素小於2個的情況，這一步很重要，在每次計算時都檢查當時的條件是否能計算，一旦錯誤，立刻break，這樣即使有錯誤的輸入，WINDOWS也不會報錯而導致程序異常結束，即動態的實現了跟蹤表達式的計算機，最後，檢查一下壓棧次數和出棧次數是否滿足某一公式（具體我忘記了，自己推一下）就可以判斷表達式是否合法。
類CStack的定義：
class CStack類CStack的實現：
{
private:
int num[100];//棧內元素的存放
int sum;//棧裡數據的個數
int flag;//非法操作判斷位
int popcount;//記錄POP次數
int pushcount;//記錄PUSH次數
public:
CStack();
int getflag();//提取非法操作判斷位編碼 /> int getsum();/> void setflag(int);
int getcount();//通過popcount，pushcount計算返回表達式中的數字的個數
void Pop();//出棧操作
void Push(int temp);//入棧操作
int Top();//返回棧頂元素
virtual ~CStack();
};CStack::CStack()
{
for(int i=0;i<=50;i++)
num[i]=0;
sum=0;
flag=1;//假設所有操作均合法
popcount=0;
pushcount=0;
}
int CStack::getflag()
{
return flag;
}
int CStack::getsum()
{
return sum;
}
void CStack::setflag(int tempflag)
{
flag=tempflag;
}
int CStack::getcount()
{
return (pushcount*2-popcount)/2;
}
void CStack::Pop()
{
if(sum>=1)//判斷是否非法操作
{
num[sum]=0;
sum--;
popcount++;
}
else
{
flag=0;
}
}
void CStack::Push(int temp)
{
sum++;
num[sum]=temp;
pushcount++;
}
int CStack::Top()
{
if(sum>=1)//判斷是否非法操作
{
return num[sum];
}
else
{
flag=0;
}
}
主程序,這裡完成了計算，以及對表達式檢驗的全部過程：
void CB05031126Dlg::OnCalculate()
{
// TODO: Add your control notification handler code here
UpdateData(TRUE);
m_expression.TrimLeft();
m_expression.TrimRight();
m_expression=trimblank(m_expression);
CStack s;
int i=0;
int j,k;
int ntemp;//臨時操作數
int ntemp1;//臨時操作數
int ntemp2;//臨時操作數
int result;//運算結果
//int opNum=getop(m_expression);
if(check(m_expression)==1)//檢驗非法字符
{
while((i<m_expression.GetLength())&&(s.getflag()!=0))
{
if((m_expression[i]==''+'')||
(m_expression[i]==''-'')||
(m_expression[i]==''*'')||
(m_expression[i]==''/''))
{
if(m_expression[i]==''+'')//完成加法運算
{
ntemp1=s.Top();
s.Pop();
ntemp2=s.Top();
s.Pop();
ntemp=ntemp1+ntemp2;
s.Push(ntemp);
}
if(m_expression[i]==''-'')//完成減法運算
{
ntemp1=s.Top();
s.Pop();
ntemp2=s.Top();
s.Pop();
ntemp=ntemp2-ntemp1;
s.Push(ntemp);
}
if(m_expression[i]==''*'')//完成乘法運算
{
ntemp1=s.Top();
s.Pop();
ntemp2=s.Top();
s.Pop();
ntemp=ntemp1*ntemp2;
s.Push(ntemp);
}
if(m_expression[i]==''/'')//完成除法運算
{
ntemp1=s.Top();
s.Pop();
ntemp2=s.Top();
s.Pop();
if(ntemp1!=0)
{
ntemp=ntemp2/ntemp1;
s.Push(ntemp);
}
else
{
s.setflag(0);
}
}
k=k+2;
}
else
{
ntemp=m_expression[i]-48;
k=i+1;
while((k<m_expression.GetLength())&&
(m_expression[k]!='' '')&&
(m_expression[k]!=''+'')&&
(m_expression[k]!=''-'')&&
(m_expression[k]!=''*'')&&
(m_expression[k]!=''/''))
{
k++;
}
for(j=i+1;j<k;j++)
//講表達式中的數字字符轉換為整型
ntemp=ntemp*10+(m_expression[j]-''0'');
s.Push(ntemp);
}
i=k+1;
}
if((s.getflag()!=0)&&(s.getcount()-getop(m_expression)==1)&&(s.getsum()==1))
{
result=s.Top();
m_result.Format("%d",result);
UpdateData(FALSE);
}
else
{
MessageBox("表達式錯誤！請重新輸入！");
}
}
else
{
MessageBox("表達式錯誤！請重新輸入！");
}
}
附言：
本程序為南京郵電大學軟件工程專業程序設計實驗，我在做的時候附加實現了對表達式的校驗，理論上應該可以檢測出任何錯誤的表達式。
本文配套源碼
