后缀表达式求值及校验

后缀表达式求值及校验

作者：吴登荣

下载源代码

摘要：

　　本程序是一个完整的后缀表达式计算，主要用栈的操作实现，本程序封装了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
{
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 hereUpdateData(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("表达式错误！请重新输入！");}}

本程序为南京邮电大学软件工程专业程序设计实验，我在做的时候附加实现了对表达式的校验，理论上应该可以检测出任何错误的表达式。