鱼C论坛

 找回密码
 立即注册
查看: 3551|回复: 14

关于中缀转后缀与逆波兰合二为一的代码怎么写

[复制链接]
发表于 2020-3-2 14:38:02 | 显示全部楼层 |阅读模式

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

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

x
【问题描述】表达式求值,栈的应用,给定一个以“#”作为结束符的算式,求出算式的结果

【输入形式】以“#”结尾的表达式,运算数为正数。每个表达式占一行。

【输出形式】输出表达式运算的结果,输出数据请保留2位小数。

【样例输入】

4+2.53*3-10/5#

3*(7.91-2)#

2.4*3.6/2#

【样例输出】

9.59

17.73

4.32
主要是怎么输入小数也能满足?求求大佬们,已经快被这题逼疯了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2020-3-2 15:02:03 | 显示全部楼层
“主要是怎么输入小数也能满足?”
是什么意思?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-3-2 19:23:39 | 显示全部楼层
人造人 发表于 2020-3-2 15:02
“主要是怎么输入小数也能满足?”
是什么意思?

就是我写的时候,输入的中缀表达式里面的数字只能是整数,比如说我可以输入1+2,但是我如果想输入1.2+3.3这样子的话就不会了,现在我想让我的输入里面既可以输入运算符像加减乘除,还可以是数字包括整数和小数,最终也能计算出答案
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-3-2 19:50:39 | 显示全部楼层
F0T1024 发表于 2020-3-2 19:23
就是我写的时候,输入的中缀表达式里面的数字只能是整数,比如说我可以输入1+2,但是我如果想输入1.2+3.3 ...

把你的代码贴出来
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-3-3 09:06:37 | 显示全部楼层
我是按照小甲鱼在数据结构与算法的视频里面讲的来写的两段代码
第一段是中缀转后缀的:
#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>

#define MAXSIZE 20
#define STACKINCREMENT 10
#define MAXBUFFER 10//最大缓冲区

typedef char ElemType;
typedef struct
{
        ElemType* base;
        ElemType* top;
        int StackSize;
}sqStack;

void InitStack(sqStack* S)
{
        S->base = (ElemType *)malloc(MAXSIZE * sizeof(ElemType));
        //或S.base = (int*)malloc(MAXSIZE*sizeof(int));
        if (!S->base)
                exit(0);//存储分配失败

        S->top = S->base;//栈顶指针等于栈底指针
        S->StackSize = MAXSIZE;
}

void Push(sqStack* S, ElemType e)
{
        if ((S->top) - (S->base) >= (S->StackSize))//栈满或超出
        {
                S->base = (ElemType *)realloc(S->base, (S->StackSize + STACKINCREMENT) * sizeof(ElemType));//增加空间
                if (!S->base)
                        exit(0);

                S->top = (S->base) + (S->StackSize);
                S->StackSize = S->StackSize + STACKINCREMENT;
        }

        //*S->top++ = e;
        *(S->top) = e;
        S->top++;
}


void Pop(sqStack* S, ElemType* e)
{
        if (S->top == S->base)
                return;
        /*--S->top;
        *e = *(S->top);*/
        *e = *--(S->top);//将栈顶元素弹出并修改栈顶指针
}

int StackLen(sqStack s)
{
        return (s.top - s.base);
}

int main(void)
{
        sqStack s;
        char c, e;

        InitStack(&s);

        printf("请输入中缀表达式,以#作为结束标志:");
        scanf("%c", &c);

        while (c != '#')
        {
                while(c >= '0' && c <= '9')
                {
                        printf("%c", c);
                        scanf("%c",&c);
                        if(c<'0' || c>'9')
            {
                printf(" ");
            }
                }
                if (')' == c)
                {
                        Pop(&s,&e);
                        while ('(' != e)
                        {
                                printf("%c ", e);
                                Pop(&s, &e);
                        }
                }
                else if ('+' == c || '-' == c)
                {
                        if (!StackLen(s))//为空
                        {
                                Push(&s, c);
                        }
                        else
                        {
                                do
                                {
                                        Pop(&s, &e);
                                        if ('(' == e)
                                        {
                                                Push(&s, e);
                                        }
                                        else
                                        {
                                                printf("%c ", e);
                                        }
                                } while (StackLen(s) && '(' != e );
                                Push(&s, c);
                        }
                }
                else if ('*' == c || '/' == c || '(' == c)
                {
                        Push(&s, c);
                }
                else if('#' == c)
        {
            break;
        }
                else
                {
                        printf("\n出错:输入格式错误!\n");
                        return -1;
                }

                scanf("%c", &c);
        }

        while (StackLen(s))//不为空
        {
                Pop(&s, &e);
                printf("%c ", e);
        }
        //system("pause");
        return 0;
}

第二段是逆波兰:
#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>


#define MAXSIZE 20
#define STACKINCREMENT 10
#define MAXBUFFER 10//最大缓冲区

typedef double ElemType;
typedef struct
{
        ElemType* base;
        ElemType* top;
        int StackSize;
}sqStack;

void InitStack(sqStack* S)
{
        S->base = (ElemType *)malloc(MAXSIZE * sizeof(ElemType));
        //或S.base = (int*)malloc(MAXSIZE*sizeof(int));
        if (!S->base)
                exit(0);//存储分配失败

        S->top = S->base;//栈顶指针等于栈底指针
        S->StackSize = MAXSIZE;
}

void Push(sqStack* S, ElemType e)
{
        if (S->top - S->base >= S->StackSize)//栈满或超出
        {
                S->base = (ElemType*)realloc(S->base, (S->StackSize + STACKINCREMENT) * sizeof(ElemType));//增加空间
                if (!S->base)
                        exit(0);

                S->top = S->base + S->StackSize;
                S->StackSize = S->StackSize + STACKINCREMENT;
        }

        //*S->top++ = e;
        *(S->top) = e;
        S->top++;
}

void Pop(sqStack* S, ElemType* e)
{
        if (S->top == S->base)
                return;
        /*--S->top;
        *e = *(S->top);*/
        *e = *--(S->top);//将栈顶元素弹出并修改栈顶指针
}

int StackLen(sqStack S)
{
        return (S.top - S.base);
}

int main(void)
{
        sqStack s;
        char c;
        double d, e;
        char str[MAXBUFFER];
        int i = 0;

        InitStack(&s);

        printf("请按逆波兰表达式输入待计算数据,数据与运算符之间用空格隔开,以#作为结束标志:\n");
        scanf("%c",&c);

        while (c != '#')
        {
                while(isdigit(c) || c == '.')//用于过滤数字,头文件为ctype.h
                {
                        str[i++] = c;
                        str[i] = '\0';
                        if (i >= 10)
                        {
                                printf("出错:输入的单个数据过大\n");
                                return -1;
                        }
                        scanf("%c",&c);
                        if (c == ' ')
                        {
                                d = atof(str);//将字符串转化为浮点数,返回值为double型,头文件为stdlib.h
                                Push(&s, d);
                                i = 0;
                                break;
                        }
                }
                switch (c)
                {
                case '+':
                        Pop(&s, &e);
                        Pop(&s, &d);
                        Push(&s, d + e);
                        break;
                case '-':
                        Pop(&s, &e);
                        Pop(&s, &d);
                        Push(&s, d - e);
                        break;
                case '*':
                        Pop(&s, &e);
                        Pop(&s, &d);
                        Push(&s, d * e);
                        break;
                case '/':
                        Pop(&s, &e);
                        Pop(&s, &d);
                        if (e != 0)
                        {
                                Push(&s, d / e);
                        }
                        else
                        {
                                printf("\n出错:除数为零! \n");
                                return -1;
                        }
                        break;

                }
                scanf("%c",&c);
        }

        Pop(&s, &d);
        printf("%f",d);

        system("pause");
        return 0;
}
现在我的问题有两个,一个是怎么把这两段代码合二为一,一个是改变我的输入形式,变成我之前的要求
感谢!!!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-3-3 16:35:41 | 显示全部楼层
F0T1024 发表于 2020-3-3 09:06
我是按照小甲鱼在数据结构与算法的视频里面讲的来写的两段代码
第一段是中缀转后缀的:
#include

你直接在你发的帖子下面回复,我根本就没有收到通知
这也是我点进来才看到
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-3-4 01:36:52 | 显示全部楼层
我仔细想了想,要把这两个程序合并成一个,并且实现你的需求
需要对这两个代码做大量的修改,我觉得这还不如重写一个
我估计修改这两个代码到完成你的需求后,这个代码就和重写了差不多了,所以我不想修改这个代码
我试试重写一个吧,可以吧?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-3-5 09:58:23 | 显示全部楼层
人造人 发表于 2020-3-4 01:36
我仔细想了想,要把这两个程序合并成一个,并且实现你的需求
需要对这两个代码做大量的修改,我觉得这还不 ...

非常感谢大佬
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-3-5 17:40:51 | 显示全部楼层
postfix_expression.tar.zip (25.21 KB, 下载次数: 29)
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-3-6 15:52:56 | 显示全部楼层

大佬,我在测试数据时出现了异常,显示在stack.c文件中
stack_elem_t stack_top(stack_t s)
{
    return s->top->data;//这一行显示有未经处理的异常,读取位置发生冲突
}
不知道该怎么解决
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-3-6 17:36:22 | 显示全部楼层
F0T1024 发表于 2020-3-6 15:52
大佬,我在测试数据时出现了异常,显示在stack.c文件中
stack_elem_t stack_top(stack_t s)
{

qq: 1440332527
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-3-6 17:37:31 | 显示全部楼层
F0T1024 发表于 2020-3-6 15:52
大佬,我在测试数据时出现了异常,显示在stack.c文件中
stack_elem_t stack_top(stack_t s)
{

我猜可能是因为在栈空的时候访问了栈顶元素,^_^
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-3-10 15:24:24 | 显示全部楼层
使用了类模板, C++
#ifndef STACK_H
#define STACK_H

#include <stdlib.h>
#include <stdio.h>
#include <stack>
#define MAXSIZE 20
#define STACKINCREMENT 10

// define element type

//typedef double ElemType;
template<class T>
struct Node
{
    T *base;
    T *top;
    int stackSize;
};


template<class T>
class Stack
{

public:
    Stack(struct Node<T> *S)
    {
        this->S = S;
        initStack();
    }
    Stack(){}

    void initStack()
    {
        S->base = (T *)malloc(MAXSIZE *sizeof(T));
        if(!S->base)
        {
            printf("alloc failure\n");
            exit(-1);
        }
        S->top = S->base;
        S->stackSize = MAXSIZE;
    }
    void initStack(struct Node<T>*S)
    {
        this->S = S;
        initStack();
    }

    void push(T e)
    {
        // stack is full
        if((S->top) - (S->base) >= (S->stackSize))
        {
            S->base = (T*)realloc(S->base, (S->stackSize + STACKINCREMENT)*sizeof(T));
            if(!S->base)
            {
                printf("realloc failure\n");
                exit(-1);
            }
            S->top = (S->base) +(S->stackSize);
            S->stackSize = S->stackSize + STACKINCREMENT;
        }
        *(S->top) = e;
        S->top++;
    }
    void pop(T *e)
    {
        if(S->top == S->base)
        {
            printf("stack is empty\n");
            return;
        }
        // top always point is empty, so must S->top--;
        *e = *--(S->top);
    }
    int stackLen(void)
    {
        return (S->top-S->base);
    }

private:
    struct Node<T> *S;
};

#endif // STACK_H
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-3-10 15:24:59 | 显示全部楼层
逆波兰实现
#ifndef POLANDOPERATOR_H
#define POLANDOPERATOR_H
#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
#include "stack.h"

#define MAX_BUFF_VOLUMN 16

template<class T>
class PolandOperator
{
public:
    PolandOperator(Stack<T> *S)
    {
        this->stack = S;
    }

    T getResult(char *buff)
    {
        char str[MAX_BUFF_VOLUMN] = {0};
        char *p = buff;
        int i = 0;
        T d, e;
        while(*p != '\0')
        {
            // filter digit
            while(isdigit(*p) || *p == '.')
            {
                str[i++] = *p;
                // use to end
                str[i] = '\0';
                if(i >=  MAX_BUFF_VOLUMN)
                {
                    printf("error, this number is too big\n");
                    return -1;
                }
                p++;
                //space
                if(*p == 32)
                {
                    d = atof(str);
                    stack->push(d);
                    i = 0;
                    break;
                }
            }
            switch (*p) {
            case '+':
                stack->pop(&e);
                stack->pop(&d);
                stack->push(d+e);
                break;
            case '-':
                stack->pop(&e);
                stack->pop(&d);
                stack->push(d-e);
                break;
            case '*':
                stack->pop(&e);
                stack->pop(&d);
                stack->push(d*e);
                break;
            case '/':
                stack->pop(&e);
                stack->pop(&d);
                if(e != 0)
                {
                    stack->push(d/e);
                }
                else
                {
                    printf("\n error, zero\n");
                    return -1;
                }
                break;
            }
            p++;
        }
        stack->pop(&d);
        return d;
    }

    void getPolandExpression(char *buff, char *ret)
    {
        char*p = buff;
        char e;
        while(*p != '\0')
        {
            while((*p >= '0' && *p <= '9') || *p == '.')
            {
                *ret++ = *p++;
            }
            *ret = 32;
            ret++;
            if(')' == *p)
            {
                stack->pop(&e);
                while('(' != e)
                {
                    *ret++ = e;
                    *ret++ = 32;
                    stack->pop(&e);
                }
            }
            else if('+' == *p || '-' == *p)
            {
                if(!stack->stackLen())
                {
                    stack->push(*p);
                }
                else
                {
                    do
                    {
                        stack->pop(&e);
                        if('(' == e)
                        {
                            stack->push(e);
                        }
                        else
                        {
                            *ret++ = e;
                            *ret++ = 32;
                        }
                    }while(stack->stackLen() && '(' != e);
                    stack->push(*p);
                }
            }
            else if('*' == *p || '/' == *p || '(' == *p)
            {
                stack->push(*p);
            }
            p++;
        }
        while (stack->stackLen()) {
            stack->pop(&e);
            *ret++ = e;
            *ret++ = 32;
        }
        *ret = '\0';
    }

 private:
    Stack<T> *stack;
};

#endif // POLANDOPERATOR_H
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-3-10 15:25:51 | 显示全部楼层
本帖最后由 代号-K 于 2020-3-11 18:51 编辑

实现方法
typedef double Element;
typedef char ConvertEle;
//convert polandExpression
    char retArray[64] = {0};
    char buff[32] = "2.4*3.6/2";
    struct Node<ConvertEle> s1;
    Stack<ConvertEle> stack1(&s1);
    PolandOperator<ConvertEle> pld1(&stack1);
    pld1.getPolandExpression(buff, retArray);
    char *p = retArray;
    while(*p != '\0')
    {
        printf("%c",*p);
        p++;
    }
    printf("\n");

    //computer polandExpression
    struct Node<Element> s;
    Stack<Element> stack(&s);
    PolandOperator<Element> pld(&stack);
    double ret = pld.getResult(retArray);
    printf("%f\n", ret);
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

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

本版积分规则

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

GMT+8, 2024-6-19 01:12

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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