中缀C代码的后缀中存在分段错误

0yg35tkg  于 2022-12-03  发布在  其他
关注(0)|答案(1)|浏览(149)

I'm writing a code to convert postfix to infix. but when i try to print the stack elements to check it it's not showing any thing. in the push function it prints the top element, but the display function only shows the top element no matter what. and there is segmentation fault after the line strcat(nn,y) .The input i tried was 09+ .

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define MAX 20

char *stk[MAX], a[MAX];
int t = -1;

void push(char x[]);
void pop();
void display();

int main()
{
    int i = 0;

    char *x, *y, nn[MAX];
    printf("enter expression:");
    gets(a);

    while (a[i] != '\0')
    {
        if (isdigit(a[i]))
        {
            push((char [2]){ a[i], '\0' });
        }
        else
        {
            display();
            pop();
            x = stk[t];

            pop();
            y = stk[t];

            strcpy(nn, "");
            strcat(nn, "(");
            strcat(nn, y);
            strcat(nn, (char [2]){ a[i], '\0' });
            strcat(nn, x);
            strcat(nn, ")");

            push(nn);

        }

        i++;
    }

    printf("%s", stk[0]);
}

void push(char x[])
{
    t = t + 1;
    stk[t] = x;
    printf("curtop %d:%s\n", t, stk[t]);
}

void pop()
{
    t = t - 1;
}

void display()
{
    printf("%s:%s", stk[t], stk[t - 1]);
}
ohtdti5x

ohtdti5x1#

我将重申这些评论,加上一些参考资料,并补充一些我自己的想法。
你应该做的第一件事是阅读Why is the gets function so dangerous that it should not be used?gets被从C11语言中删除,任何半现代的工具链都不应该包括它:

example.c:5:9: warning: implicit declaration of function ‘gets’; did you mean ‘fgets’? [-Wimplicit-function-declaration]

fgets是建议的替代项。请使用它。
两者均为compound literals

(char [2]){ a[i], '\0' }

这意味着每个对象的lifetime在它们各自的封闭块结束时结束。
因此,您正在将一个即将出现的dangling pointer推送到堆栈上。
这是Undefined Behaviour的一个示例。
以下

push(nn);

重复将指向nn的第一个元素的同一指针推入堆栈。该指针值始终相同,并且始终指向数组的 * 当前 * 内容,该内容不断更改。
这两个问题都可以通过使用dynamic memory创建推入堆栈的字符串的副本来解决。
nn(中缀表达式缓冲区)与a(后缀表达式缓冲区)大小相同,但两者都太小。
请记住,要在缓冲区中存储字符串,缓冲区的大小必须至少为字符串的长度加1(对于null terminating byte)。
后缀表达式

09+6+10*+63-/

的字符串长度为13,适合a

((((0+9)+6)+(1*0))/(6-3))

其字符串长度为25。这不适用于nn,并且strcat无法防止缓冲区溢出。
这将是Undefined Behaviour的另一个示例。
作为设计的一个要点

pop();
x = stk[t];

是笨拙的。
虽然文件作用域变量(全局变量)的使用和围绕它们的函数是一个非常common way的数据结构,但您仍然应该致力于实现更接近abstract data type的东西。
pop应该 * 返回 * 堆栈的最顶层元素,作为pop函数的 * 用户 *,您不应该关心如何管理它,只应该关心它是否按预期行为。

char *x = pop();

下一步是删除文件作用域变量,以便程序中可以同时存在多个堆栈。
下面是一个粗略的示例程序,它解决了所讨论的大多数问题。注意,它解析输入的方式略有不同,使用whitespace as a delimiter。它遵循括号的规则。
它不验证操作数或生成的表达式。操作数可以长于一个字符。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define BUF_SIZE 256
#define SEP " \r\n"
#define STACK_INIT { 0 }
#define STACK_MAX 64

struct stack {
    size_t height;
    char *data[STACK_MAX];
};

size_t count(struct stack *s)
{
    return s->height;
}

int push(struct stack *s, const char *item)
{
    if (s->height >= STACK_MAX)
        return 0;

    char *copy = malloc(1 + strlen(item));

    if (!copy)
        return 0;

    strcpy(copy, item);
    s->data[s->height++] = copy;

    return 1;
}

char *pop(struct stack *s)
{
    return s->height ? s->data[--s->height] : NULL;
}

void free_stack(struct stack *s)
{
    char *item;

    while ((item = pop(s)))
        free(item);
}

int main(void)
{
    char buffer[BUF_SIZE];
    printf("enter expression: ");
    fflush(stdout);

    if (!fgets(buffer, sizeof buffer, stdin)) {
        if (ferror(stdin))
            perror("reading stdin");

        return EXIT_FAILURE;
    }

    struct stack tokens = STACK_INIT;
    char *tok = strtok(buffer, SEP);

    while (tok) {
        char expr[BUF_SIZE * 2];
        /* is the first and only character an operator? */
        int is_op = strchr("+-/*", *tok) && !tok[1];

        if (is_op) {
            if (count(&tokens) < 2) {
                fprintf(stderr, "Operator (%c) needs two operands.\n", *tok);
                free_stack(&tokens);
                return EXIT_FAILURE;
            }

            char *rhs = pop(&tokens);
            char *lhs = pop(&tokens);

            if (snprintf(expr, sizeof expr, "(%s %c %s)", lhs, *tok, rhs) >= sizeof expr)
                fprintf(stderr, "Warning: expression truncated.\n");

            free(rhs);
            free(lhs);
        }

        if (!push(&tokens, is_op ? expr : tok)) {
            fprintf(stderr, "Failed to push stack item.\n");
            free_stack(&tokens);
            return EXIT_FAILURE;
        }

        tok = strtok(NULL, SEP);
    }

    for (char *s; (s = pop(&tokens)); free(s))
        printf("%s\n", s);
}

相关问题