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

F0T1024

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

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

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

【样例输入】

4+2.53*3-10/5#

3*(7.91-2)#

2.4*3.6/2#

【样例输出】

9.59

17.73

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

人造人

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

F0T1024

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

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

人造人

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

把你的代码贴出来

F0T1024

我是按照小甲鱼在数据结构与算法的视频里面讲的来写的两段代码
第一段是中缀转后缀的：
#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;
}
现在我的问题有两个，一个是怎么把这两段代码合二为一，一个是改变我的输入形式，变成我之前的要求
感谢！！！

人造人

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

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

人造人

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

F0T1024

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

非常感谢大佬

人造人

postfix_expression.tar.zip (25.21 KB, 下载次数: 29)

2020-3-5 17:40 上传

点击文件名下载附件

F0T1024

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

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

人造人

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

qq: 1440332527

人造人

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

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

代号-K

使用了类模板， C++

1. #ifndef STACK_H
   
2. #define STACK_H
   
3. 
   
4. #include <stdlib.h>
   
5. #include <stdio.h>
   
6. #include <stack>
   
7. #define MAXSIZE 20
   
8. #define STACKINCREMENT 10
   
9. 
   
10. // define element type
    
11. 
    
12. //typedef double ElemType;
    
13. template<class T>
    
14. struct Node
    
15. {
    
16.     T *base;
    
17.     T *top;
    
18.     int stackSize;
    
19. };
    
20. 
    
21. 
    
22. template<class T>
    
23. class Stack
    
24. {
    
25. 
    
26. public:
    
27.     Stack(struct Node<T> *S)
    
28.     {
    
29.         this->S = S;
    
30.         initStack();
    
31.     }
    
32.     Stack(){}
    
33. 
    
34.     void initStack()
    
35.     {
    
36.         S->base = (T *)malloc(MAXSIZE *sizeof(T));
    
37.         if(!S->base)
    
38.         {
    
39.             printf("alloc failure\n");
    
40.             exit(-1);
    
41.         }
    
42.         S->top = S->base;
    
43.         S->stackSize = MAXSIZE;
    
44.     }
    
45.     void initStack(struct Node<T>*S)
    
46.     {
    
47.         this->S = S;
    
48.         initStack();
    
49.     }
    
50. 
    
51.     void push(T e)
    
52.     {
    
53.         // stack is full
    
54.         if((S->top) - (S->base) >= (S->stackSize))
    
55.         {
    
56.             S->base = (T*)realloc(S->base, (S->stackSize + STACKINCREMENT)*sizeof(T));
    
57.             if(!S->base)
    
58.             {
    
59.                 printf("realloc failure\n");
    
60.                 exit(-1);
    
61.             }
    
62.             S->top = (S->base) +(S->stackSize);
    
63.             S->stackSize = S->stackSize + STACKINCREMENT;
    
64.         }
    
65.         *(S->top) = e;
    
66.         S->top++;
    
67.     }
    
68.     void pop(T *e)
    
69.     {
    
70.         if(S->top == S->base)
    
71.         {
    
72.             printf("stack is empty\n");
    
73.             return;
    
74.         }
    
75.         // top always point is empty, so must S->top--;
    
76.         *e = *--(S->top);
    
77.     }
    
78.     int stackLen(void)
    
79.     {
    
80.         return (S->top-S->base);
    
81.     }
    
82. 
    
83. private:
    
84.     struct Node<T> *S;
    
85. };
    
86. 
    
87. #endif // STACK_H
    

复制代码

代号-K

逆波兰实现

1. #ifndef POLANDOPERATOR_H
   
2. #define POLANDOPERATOR_H
   
3. #include <stdlib.h>
   
4. #include <stdio.h>
   
5. #include <ctype.h>
   
6. #include "stack.h"
   
7. 
   
8. #define MAX_BUFF_VOLUMN 16
   
9. 
   
10. template<class T>
    
11. class PolandOperator
    
12. {
    
13. public:
    
14.     PolandOperator(Stack<T> *S)
    
15.     {
    
16.         this->stack = S;
    
17.     }
    
18. 
    
19.     T getResult(char *buff)
    
20.     {
    
21.         char str[MAX_BUFF_VOLUMN] = {0};
    
22.         char *p = buff;
    
23.         int i = 0;
    
24.         T d, e;
    
25.         while(*p != '\0')
    
26.         {
    
27.             // filter digit
    
28.             while(isdigit(*p) || *p == '.')
    
29.             {
    
30.                 str[i++] = *p;
    
31.                 // use to end
    
32.                 str[i] = '\0';
    
33.                 if(i >=  MAX_BUFF_VOLUMN)
    
34.                 {
    
35.                     printf("error, this number is too big\n");
    
36.                     return -1;
    
37.                 }
    
38.                 p++;
    
39.                 //space
    
40.                 if(*p == 32)
    
41.                 {
    
42.                     d = atof(str);
    
43.                     stack->push(d);
    
44.                     i = 0;
    
45.                     break;
    
46.                 }
    
47.             }
    
48.             switch (*p) {
    
49.             case '+':
    
50.                 stack->pop(&e);
    
51.                 stack->pop(&d);
    
52.                 stack->push(d+e);
    
53.                 break;
    
54.             case '-':
    
55.                 stack->pop(&e);
    
56.                 stack->pop(&d);
    
57.                 stack->push(d-e);
    
58.                 break;
    
59.             case '*':
    
60.                 stack->pop(&e);
    
61.                 stack->pop(&d);
    
62.                 stack->push(d*e);
    
63.                 break;
    
64.             case '/':
    
65.                 stack->pop(&e);
    
66.                 stack->pop(&d);
    
67.                 if(e != 0)
    
68.                 {
    
69.                     stack->push(d/e);
    
70.                 }
    
71.                 else
    
72.                 {
    
73.                     printf("\n error, zero\n");
    
74.                     return -1;
    
75.                 }
    
76.                 break;
    
77.             }
    
78.             p++;
    
79.         }
    
80.         stack->pop(&d);
    
81.         return d;
    
82.     }
    
83. 
    
84.     void getPolandExpression(char *buff, char *ret)
    
85.     {
    
86.         char*p = buff;
    
87.         char e;
    
88.         while(*p != '\0')
    
89.         {
    
90.             while((*p >= '0' && *p <= '9') || *p == '.')
    
91.             {
    
92.                 *ret++ = *p++;
    
93.             }
    
94.             *ret = 32;
    
95.             ret++;
    
96.             if(')' == *p)
    
97.             {
    
98.                 stack->pop(&e);
    
99.                 while('(' != e)
    
100.                 {
     
101.                     *ret++ = e;
     
102.                     *ret++ = 32;
     
103.                     stack->pop(&e);
     
104.                 }
     
105.             }
     
106.             else if('+' == *p || '-' == *p)
     
107.             {
     
108.                 if(!stack->stackLen())
     
109.                 {
     
110.                     stack->push(*p);
     
111.                 }
     
112.                 else
     
113.                 {
     
114.                     do
     
115.                     {
     
116.                         stack->pop(&e);
     
117.                         if('(' == e)
     
118.                         {
     
119.                             stack->push(e);
     
120.                         }
     
121.                         else
     
122.                         {
     
123.                             *ret++ = e;
     
124.                             *ret++ = 32;
     
125.                         }
     
126.                     }while(stack->stackLen() && '(' != e);
     
127.                     stack->push(*p);
     
128.                 }
     
129.             }
     
130.             else if('*' == *p || '/' == *p || '(' == *p)
     
131.             {
     
132.                 stack->push(*p);
     
133.             }
     
134.             p++;
     
135.         }
     
136.         while (stack->stackLen()) {
     
137.             stack->pop(&e);
     
138.             *ret++ = e;
     
139.             *ret++ = 32;
     
140.         }
     
141.         *ret = '\0';
     
142.     }
     
143. 
     
144. private:
     
145.     Stack<T> *stack;
     
146. };
     
147. 
     
148. #endif // POLANDOPERATOR_H
     

复制代码

代号-K

实现方法

1. 
   
2. typedef double Element;
   
3. typedef char ConvertEle;
   
4. //convert polandExpression
   
5.     char retArray[64] = {0};
   
6.     char buff[32] = "2.4*3.6/2";
   
7.     struct Node<ConvertEle> s1;
   
8.     Stack<ConvertEle> stack1(&s1);
   
9.     PolandOperator<ConvertEle> pld1(&stack1);
   
10.     pld1.getPolandExpression(buff, retArray);
    
11.     char *p = retArray;
    
12.     while(*p != '\0')
    
13.     {
    
14.         printf("%c",*p);
    
15.         p++;
    
16.     }
    
17.     printf("\n");
    
18. 
    
19.     //computer polandExpression
    
20.     struct Node<Element> s;
    
21.     Stack<Element> stack(&s);
    
22.     PolandOperator<Element> pld(&stack);
    
23.     double ret = pld.getResult(retArray);
    
24.     printf("%f\n", ret);

复制代码