鱼C论坛

 找回密码
 立即注册
查看: 2449|回复: 0

[学习笔记] C++逆波兰表达式 简单实现(未封装)

[复制链接]
发表于 2017-7-20 20:54:12 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

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

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

#define  STACK_INIT_SIZE 100  //初始化栈空间大小
#define  SATCKINCREMENT  20   //每次栈重新申请增加的大小

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::string  c;
        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笔记

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-28 22:08

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表