浙江财经大学
信工学院ACM集训队

计算中缀表达式的值(类实现)

本文由 Ocrosoft 于 2016-04-27 11:44:05 发表

上一篇用的是STL中的<stack>,这次再用自定义的两个类来实现求值。

(输出的中缀表达式不含空格,数字以“#”结尾,可自行修改)

Solution:

#include <bits/stdc++.h>
using namespace std;
const int MaxSize=100;
double v;
template <typename T>
class SqStackClass
{
    T *data;
    int top;
public:
    SqStackClass();
    ~SqStackClass();
    bool StackEmpty();
    bool Push(T e);
    bool Pop(T &e);
    bool GetTop(T &e);
};

template <typename T>
SqStackClass<T>::SqStackClass()              //构造函数
{
    data=new T[MaxSize];     //为data分配栈空间
    top=-1;      //栈顶指针初始化
}
template <typename T>
SqStackClass<T>::~SqStackClass()  //析构函数
{
    delete [] data;
}
template <typename T>
bool SqStackClass<T>::StackEmpty()       //判断栈是否为空
{
    return(top==-1);
}
template <typename T>
bool SqStackClass<T>::Push(T e)   //进栈算法
{
    if (top == MaxSize-1)  //栈满时返回false
        return false;
    top++;        //栈顶指针增1
    data[top]=e;                                          //将x进栈
    return true;
}
template <typename T>
bool SqStackClass<T>::Pop(T &e)             //出栈算法
{
    if (StackEmpty())   //栈为空的情况,即栈下溢出
        return false;
    e=data[top];     //取栈顶指针元素的元素
    top--;   //栈顶指针减1
    return true;
}
template <typename T>
bool SqStackClass<T>::GetTop(T &e)      //取栈顶元素算法
{
    if (StackEmpty())  //栈为空的情况,即栈下溢出
        return false;
    e=data[top];     //取栈顶指针位置的元素
    return true;
}
class ExpressClass
{
public:
    char *exp;        //存放中缀表达式
    char postexp[MaxSize];   //存放后缀表达式
    int pnum; //postexp中字符个数public:
    void Setexp(char *str)
    {
        exp=new char();
        strcpy(exp,str);
    }
    void Disppostexp()
    {
        puts(postexp);
    }
    void Trans()
    {
        char ch,e;
        int i=0,j=0;
        SqStackClass<char> sop;
        while(!sop.StackEmpty())
            sop.Pop(e);
        while(exp[i])
        {
            ch=exp[i];
            if(ch=='(')
                sop.Push(ch);
            else if(ch==')')
            {
                while(!sop.StackEmpty()&&sop.GetTop(e)&&e!='(')
                {
                    sop.GetTop(e);
                    postexp[j++]=e;
                    sop.Pop(e);
                }
                sop.Pop(e);
            }
            else if(ch=='+'||ch=='-')
            {
                while(!sop.StackEmpty()&&sop.GetTop(e)&&e!='(')
                {
                    sop.GetTop(e);
                    postexp[j++]=e;
                    sop.Pop(e);
                }
                sop.Push(ch);
            }
            else if(ch=='*'||ch=='/')
            {
                while(!sop.StackEmpty()&&sop.GetTop(e)&&e!='('&&(e=='*'||e=='/'))
                {
                    sop.GetTop(e);
                    postexp[j++]=e;
                    sop.Pop(e);
                }
                sop.Push(ch);
            }
            else
            {
                while(ch>='0'&&ch<='9')
                {
                    postexp[j++]=ch;
                    i++;
                    if(exp[i])
                        ch=exp[i];
                    else
                        break;
                }
                i--;
                postexp[j++]='#';
            }
            i++;
        }
        while(!sop.StackEmpty())
        {
            sop.GetTop(e);
            postexp[j++]=e;
            sop.Pop(e);
        }
        j--;
        postexp[j]='\0';
    }
    bool GetValue()
    {
        SqStackClass<double> st;
        double a,b,c,d;
        int i=0;
        char ch;
        int len=strlen(postexp);
        while(i<len)
        {
            ch=postexp[i];
            switch(ch)
            {
            case '+':
                st.Pop(a);
                st.Pop(b);
                c=b+a;
                st.Push(c);
                break;
            case '-':
                st.Pop(a);
                st.Pop(b);
                c=b-a;
                st.Push(c);
                break;
            case '*':
                st.Pop(a);
                st.Pop(b);
                c=b*a;
                st.Push(c);
                break;
            case '/':
                st.Pop(a);
                st.Pop(b);
                if(a!=0)
                {
                    c=b/a;
                    st.Push(c);
                }
                else
                    return false;
                break;
            default:
                d=0;
                while(ch>='0'&&ch<='9')
                {
                    d=10*d+(ch-'0');
                    i++;
                    ch=postexp[i];
                }
                st.Push(d);
            }
            i++;
        }
        st.GetTop(v);
        return true;
    }
};
int  main()
{
    ExpressClass obj;
    char str[MaxSize];
    cin>>str;
    obj.Setexp(str);
    obj.Trans();
    //obj.Disppostexp();输出后缀表达式
    obj.GetValue();
    cout<<v<<endl;
    return 0;
}

欢迎转载,请保留出处与链接。Ocrosoft » 计算中缀表达式的值(类实现)

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址