逆波兰表达式计算（后缀表达式，中缀转后缀）

/*
后缀表达式计算

中缀表达式转后缀表达式
*/
#include<iostream>
#include<cstdlib>
#include<cctype>

using namespace std;

template<class T>
class stack
{
private:
    T* base;
    T* top;
    int stackSize;
public:
    stack(int a=100):stackSize(a)
    {
        base=top=new T[stackSize];
    }
    ~stack()
    {
        delete [] base;
        base=top=NULL;
        cout<<"stack析构
";
    }
    bool is_empty()const;
    bool is_full()const;
    bool pop(T &a);
    bool push(T a);
    int len()const;
};

template<class T>
bool stack<T>::is_empty()const
{
    if(base==top)
        return true;
    else
        return false;
}

template<class T>
bool stack<T>::is_full()const
{
    if(top-base==stackSize)
        return true;
    else
        return false;
}

template<class  T>
bool stack<T>::push(T a)
{
    if(!is_full())
    {
        *(top++)=a;
        return true;
    }
    else
        return false;;
    
}

template<class T>
bool stack<T>::pop(T& a)
{
    if(!is_empty())
    {
        a=*(--top);
        return true;
    }
    else
        return false;
}

template<class T>
int stack<T>::len()const
{
    cout<<(int*)base<<endl;
    cout<<(int*)top<<endl;
    return top-base;
}

double  postfix(char* str) // 计算后缀表达式
{
    char c;
    stack<double>s;
    char bluff[10];
    
    int j=0;
    c=str[j++];
    while(c!='#')
    {
        int i=0;
        while(isdigit(c) || c=='.')//处理的数是double型的
        {
            bluff[i++]=c;// 用一块缓存区存储char型数据后转换
            
            if(i>=10)
            {
                printf("
输入的数过大
");
                return 1;
            }
            c=str[j++];
            if(' '==c) // 处理数字后的空格，符号后的空格不管
            {
                bluff[i]='';
                i=0;
                s.push(atof(bluff));
                break;
            }
        }
        if('+'==c || '-'==c || '*'==c || '/'==c)
        {
            double d,e;
            s.pop(d);
            s.pop(e);
            switch(c)
            {
            case '+':
                s.push(d+e);
                break;
            case '-':
                s.push(e-d);// 后出的减去前出的
                break;
            case '*':
                s.push(e*d);
                break;
            case '/':
                if(d !=0)
                    s.push(e/d);
                else
                {
                    printf("
除数不能为0
");
                    return 1;
                }
                break;
            default:
                printf("
符号不能识别
");
                return 1;
            }
        }

        c=str[j++];
    }
    double ans;
    s.pop(ans);
    
    return ans;    
}

char* mid2post(char* str, char*& str2)// 人机友好的中缀转换为合适计算机处理的后缀表达式
{
    int i=0,j=0;
    stack<char>s;
    char e;

    char c=str[j++];
    while(c!='#')
    {
        while(isdigit(c) || '.'==c)
        {
            str2[i++]=c;
            c=str[j++]; //看下一个数是否还是数字
            if(' '==c || '#'==c) //空格结束，这里容易出错
            {
                str2[i++]=' ';
                break;
            }
        }
        if(')'==c) //遇到右括号，栈里肯定有符号
        {
            s.pop(e);
            while('('!=e)
            {
                str2[i++]=e;
                str2[i++]=' ';
                s.pop(e);
            }
        }
        else if('+'==c || '-'==c)//
        {
            if(s.is_empty())//栈空，压栈
            {
                s.push(c);
            }
            else //里面的优先级都高于这个+-
            {
                do
                {
                    s.pop(e);//弹出前面的符号，直到栈空或者遇到左括号
                    if('('==e)
                    {
                        s.push(e);
                    }
                    else
                    {
                        str2[i++]=e;
                        str2[i++]=' ';
                    }
                }while('('!=e && !s.is_empty());
                s.push(c);// 取出来后别忘了把这个符号再压栈
            }
        }
        else if('*'==c || '/'==c || '('==c)//保证栈里的符号优先级总是较低的
        {
            s.push(c);
        }
        if('#'==c)
            break;
        c=str[j++];
    }

    while(!s.is_empty())
    {
        s.pop(e);
        str2[i++]=e;
        str2[i++]=' ';
    }
    str2[--i]='#';//'#'之前不要空格，和逆波兰表达式匹配
    str2[++i]='';
    cout<<"后缀表达式："<<str2<<endl;
    return str2;
}

double midfix(char *str)// 计算中缀表达式
{
    //cout<<str<<endl;
    char* str2=new char[100]; 
    mid2post(str,str2);

    double ans=postfix(str2);

    delete str2;

    return ans;
}



int main()
{
    char str[100];
    //printf("输入逆波兰表达式，元素之间用空格分开，并以#结束
");
    //cin.getline(str,100);
    //cout<<str<<endl;
    //printf("
计算结果是%f
",postfix(str));

    printf("输入中缀表达式，元素之间用空格分开，并以#结束
");
    cin.getline(str,100);
    cout<<midfix(str)<<endl;

    return 0;
}