关于中缀转后缀与逆波兰合二为一的代码怎么写,数据结构与算法,技术交流,鱼C论坛

F0T1024 发表于 2020-3-2 14:38:02

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

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

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

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

【样例输入】

4+2.53*3-10/5#

3*(7.91-2)#

2.4*3.6/2#

【样例输出】

9.59

17.73

4.32
主要是怎么输入小数也能满足？求求大佬们，已经快被这题逼疯了

人造人 发表于 2020-3-2 15:02:03

“主要是怎么输入小数也能满足？”
是什么意思？

F0T1024 发表于 2020-3-2 19:23:39

人造人发表于 2020-3-2 15:02
“主要是怎么输入小数也能满足？”
是什么意思？

就是我写的时候，输入的中缀表达式里面的数字只能是整数，比如说我可以输入1+2，但是我如果想输入1.2+3.3这样子的话就不会了，现在我想让我的输入里面既可以输入运算符像加减乘除，还可以是数字包括整数和小数，最终也能计算出答案

人造人 发表于 2020-3-2 19:50:39

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

把你的代码贴出来

F0T1024 发表于 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;
int i = 0;

InitStack(&s);

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

while (c != '#')
{
while(isdigit(c) || c == '.')//用于过滤数字，头文件为ctype.h
{
str = c;
str = '\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;
}
现在我的问题有两个，一个是怎么把这两段代码合二为一，一个是改变我的输入形式，变成我之前的要求
感谢！！！

人造人 发表于 2020-3-3 16:35:41

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

你直接在你发的帖子下面回复，我根本就没有收到通知
这也是我点进来才看到

人造人 发表于 2020-3-4 01:36:52

我仔细想了想，要把这两个程序合并成一个，并且实现你的需求
需要对这两个代码做大量的修改，我觉得这还不如重写一个
我估计修改这两个代码到完成你的需求后，这个代码就和重写了差不多了，所以我不想修改这个代码
我试试重写一个吧，可以吧？

F0T1024 发表于 2020-3-5 09:58:23

人造人发表于 2020-3-4 01:36
我仔细想了想，要把这两个程序合并成一个，并且实现你的需求
需要对这两个代码做大量的修改，我觉得这还不 ...

非常感谢大佬

人造人 发表于 2020-3-5 17:40:51

F0T1024 发表于 2020-3-6 15:52:56

人造人发表于 2020-3-5 17:40

大佬，我在测试数据时出现了异常，显示在stack.c文件中
stack_elem_t stack_top(stack_t s)
{
return s->top->data;//这一行显示有未经处理的异常，读取位置发生冲突
}
不知道该怎么解决

人造人 发表于 2020-3-6 17:36:22

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

qq: 1440332527

人造人 发表于 2020-3-6 17:37:31

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

我猜可能是因为在栈空的时候访问了栈顶元素，^_^

代号-K 发表于 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

代号-K 发表于 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 = {0};
   char *p = buff;
   int i = 0;
   T d, e;
   while(*p != '\0')
   {
         // filter digit
         while(isdigit(*p) || *p == '.')
         {
            str = *p;
            // use to end
            str = '\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

代号-K 发表于 2020-3-10 15:25:51

本帖最后由代号-K 于 2020-3-11 18:51 编辑

实现方法

typedef double Element;
typedef char ConvertEle;
//convert polandExpression
char retArray = {0};
char buff = "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);

页: [1]

鱼C论坛's Archiver

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