论坛 › 数据结构与算法 › C++逆波兰表达式 简单实现（未封装）

燃烧的发丝 发表于 2017-7-20 20:54:12

C++逆波兰表达式 简单实现（未封装）

本帖最后由 燃烧的发丝 于 2017-7-20 22:00 编辑

#include <iostream>
#include <string>
#include <sstream>

#defineSTACK_INIT_SIZE 100//初始化栈空间大小
#defineSATCKINCREMENT20   //每次栈重新申请增加的大小

typedef double Elemtype;

//创建栈结构
struct sqStack
{
        Elemtype *base;// 指向栈底
        Elemtype *top;        // 指向栈顶
        int stackSize;//栈大小
};

// 栈的初始化
void initStack(sqStack *s)
{
        s->base = (Elemtype*)malloc(STACK_INIT_SIZE * sizeof(Elemtype));
        if (!s->base)
        {
                exit(0);
        }
        s->top = s->base;// 最开始 栈顶级就是栈底
        s->stackSize = STACK_INIT_SIZE;       
}

//栈的压入
void push_Stack(sqStack *s, Elemtype e)
{
        //如果 栈的空间不足，就重新申请空间
        if (s->top - s->base >= s->stackSize)
        {
                //每次重新申请的空间 为原来的空间 加上SATCKINCREMENT
                s->base = (Elemtype*)realloc(s->base, (s->stackSize + SATCKINCREMENT) * sizeof(Elemtype*));
                if (!s->base)
                {
                        exit(0);
                }
                //设置栈顶
                s->top = s->base + s->stackSize;
                //设置栈的最大容量
                s->stackSize = s->stackSize + SATCKINCREMENT;
        }
        // 放入数据
        *(s->top) = e;
        // 栈顶加1
        s->top++;
}


//出栈操作
int pop_Stack(sqStack *s, Elemtype *e)
{
        if (s->top == s->base)
        {
                return -1;
        }
        //先将栈顶数据出栈，然后再将 栈顶 减1
        s->top--;
        *e = *(s->top);

        return 0;
}

//判断是否是数字
bool isnum(std::string str)
{
        std::stringstream sin(str);
        double d;
        char p;
        if (!(sin >> d))
        {
                return false;
        }
        if (sin >> p)
        {
                return false;
        }
        else
        {
                return true;
        }
}

int main()
{
        sqStack t;
        initStack(&t);

        std::cout << "请按逆波兰表达式输入待计算数据， 数据与数据之间用空格结束" << std::endl;
        std::cout << "请以#作为结束标志" << std::endl;

        std::stringc;
        double data;
        double k1, k2;

        while (std::cin >> c)
        {
                if (isnum(c))
                {
                        const char* s = c.c_str();
                        data = atof(s);
                        push_Stack(&t, data);
                        //std::cout << "压入" << data << "入栈" << std::endl;
                }
                if (c == "+")
                {
                        pop_Stack(&t, &k1);
                        pop_Stack(&t, &k2);
                        push_Stack(&t, k1 + k2);
                        //std::cout << "K1+K2 ="<<k1+k2 << std::endl;
               
                }
                if (c =="-")
                {
                        pop_Stack(&t, &k1);
                        pop_Stack(&t, &k2);
                        push_Stack(&t, k2 - k1);
                        //std::cout << "K2-K1 =" << k2-k1 << std::endl;
                }
                if (c =="*")
                {
                        pop_Stack(&t, &k1);
                        pop_Stack(&t, &k2);
                        push_Stack(&t, k2 * k1);
                        //std::cout << "K2*K2 =" << k2 * k1 << std::endl;
                }
                if (c =="/")
                {
                        if (k1 == 0)
                        {
                                std::cout << "输入错误，被除数不能为0！" << std::endl;
                        }
                        else
                        {
                                pop_Stack(&t, &k1);
                                pop_Stack(&t, &k2);
                                push_Stack(&t, k2 / k1);
                                //std::cout << "K2/K1 =" << k2 / k1 << std::endl;
                        }
                }
                if (c =="#")
                {
                        break;
                }
               
        }
        pop_Stack(&t, &data);
        std::cout << "逆波兰表达式计算结果为：" << data << std::endl;
        return 0;
}

逆波兰表达式 的实现，学习小甲鱼数据结构与算法第三章课时 27笔记

查看完整版本: C++逆波兰表达式 简单实现（未封装）