C++利用链栈实现表达式求值

以下代码由PHP站长网 52php.cn收集自互联网

现在PHP站长网小编把它分享给大家，仅供参考

 
#include<iostream.h>
typedef int Status;
typedef char Cstack;
#define OK 1
#define ERROR 0
  
typedef struct StackNode
{
    Cstack data;
    struct StackNode *next;
}StackNode,*LinkStack;
  
Status InitStack(LinkStack &S)
{
    S=NULL;
    return OK;
}
Status Push(LinkStack &S,Cstack e)
{
    StackNode *p;
    p=new StackNode;
    p->data=e;
    p->next=S;
    S=p;
    return OK;
}
Status Pop(LinkStack &S,Cstack &e)
{
    StackNode *p;
    if(S==NULL) return ERROR;
    e=S->data;
    p=S;
    S=S->next;
    delete p;
    return OK;
}
Cstack GetTop(LinkStack S)
{
    if(S!=NULL)
    return S->data;
}
Status In(Cstack ch)
{
    cin>>ch;
    if(ch=='+')
        return OK;
    else if(ch=='-')
        return OK;
    else if(ch=='*')
        return OK;
    else if(ch=='/')
        return OK;
    else if(ch=='#')
        return OK;
    else
        return ERROR;
}
Cstack Precede(Cstack t1,Cstack t2)
{
    switch(t1)
    {
    case '+':
        switch(t2)
        {
        case '+':return '>';break;
        case '-':return '>';break;
        case '*':return '<';break;
        case '/':return '<';break;
        case '(':return '<';break;
        case ')':return '>';break;
        case '#':return '>';break;
        }
        break;
        case '-':
            switch(t2)
        {
        case '+':return '>';break;
        case '-':return '>';break;
        case '*':return '<';break;
        case '/':return '<';break;
        case '(':return '<';break;
        case ')':return '>';break;
        case '#':return '>';break;
        }
        break;
        case '*':
            switch(t2)
        {
        case '+':return '>';break;
        case '-':return '>';break;
        case '*':return '>';break;
        case '/':return '>';break;
        case '(':return '<';break;
        case ')':return '>';break;
        case '#':return '>';break;
        }
        break;
        case '/':
            switch(t2)
        {
        case '+':return '>';break;
        case '-':return '>';break;
        case '*':return '>';break;
        case '/':return '>';break;
        case '(':return '<';break;
        case ')':return '>';break;
        case '#':return '>';break;
        }
        break;
        case '(':
            switch(t2)
        {
        case '+':return '<';break;
        case '-':return '<';break;
        case '*':return '<';break;
        case '/':return '<';break;
        case '(':return '<';break;
        case ')':return '=';break;
        case '#':return '>';break;
        }
        break;
        case ')':
            switch(t2)
        {
        case '+':return '>';break;
        case '-':return '>';break;
        case '*':return '>';break;
        case '/':return '>';break;
        case '(':return '=';break;
        case ')':return '>';break;
        case '#':return '>';break;
        }
        break;
        case '#':
            return '=';
        break;
    }
}
Cstack Operator(Cstack t1,Cstack t2,Cstack t3)
{
    t1=t1-48;
    t3=t3=48;
    int c;
    switch(t2)
    {
    case '+':
        c=t1+t2+48;
        return c;
        break;
    case '-':
        c=t1-t2+48;
        return c;
        break;
    case '*':
        c=t1*t2+48;
        return c;
        break;
    case '/':
        c=t1/t2+48;
        return c;
        break;
    }
}   
void main()
{
    LinkStack OPTR,OPAN;
    Cstack cha1,cha2,x,cha,thea;
    InitStack(OPTR);
    InitStack(OPAN);
    Push(OPTR,'#');
    cout<<"输入表达式的中间值及最终结果局限于0～9之间的个位数并以#号结束"<<endl;
    while(cha!='#'||GetTop(OPTR)!='#')
    {
        cin>>cha;
        if(!In(cha))
            Push(OPAN,cha);
        else
            switch(Precede(GetTop(OPTR),cha))
            {
            case '<':
                Push(OPTR,cha);
                cin>>cha;
                    break;
            case '>':
                Pop(OPTR,thea);
                Pop(OPAN,cha1);
                Pop(OPAN,cha2);
                Push(OPAN,(cha1,thea,cha2));
                    break;
            case '=':
                Pop(OPTR,x);
                break;
            }
    }
    cout<<GetTop(OPAN)<<endl;
    return;
}

以上内容由PHP站长网【52php.cn】收集整理供大家参考研究

如果以上内容对您有帮助，欢迎收藏、点赞、推荐、分享。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!