中缀到后缀

Question

我正在尝试创建一个程序来将中缀表达式转换为 post 修复并使用堆栈对其求值。三个文件如下。当我运行代码出现分段错误时。 Xcode 中的调试器说它发生在 evaluate_postfix 函数中间文件中的推送和两次弹出调用之间。谁能帮我解释为什么这是段错误？

#include <stdio.h>
#include <stdlib.h>
#include "stack.h"


stack* create_stack(void)
{
    stack* newPtr = malloc(sizeof(stack));
    newPtr->size = 0;
    newPtr->stack = NULL;

    return newPtr;
}


void push(stack *s, int val)
{
    node* newPtr = (node*) malloc(sizeof(node));
    newPtr->data = val;
    newPtr->next = s->stack;
    s->stack = newPtr;
    s->size++;
}

void pop(stack *s)
{
    node* newPtr = NULL;
    node* tempPtr = NULL;

    tempPtr = s->stack;
    newPtr = tempPtr->next;
    free(tempPtr);
    s->stack = newPtr;
    s->size--;

}


int top(stack *s)
{
    int num;
    node* newPtr = NULL;
    newPtr = s->stack;
    num = newPtr->data;

    return num;
}

int isEmpty(stack *s)
{
    if(s->stack == NULL)
    {
        return 1;
    }

    else
    {
        return 0;
    }
}

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include "stack.h"
#include <string.h>

#define MAX_EQU_LEN 100

static int prec(char operator)
{
    switch (operator)
    {
        case '*':
            return 5;
        case '/':
            return 4;
        case '%':
            return 3;
        case '+':
            return 2;
        case '-':
            return 1;
        default:
            break;
    }

    return 0;
}

static int isNumeric(char* num)
{
    if(atoi(num) == 0)
    {
        return 0;
    }
    return 1;
}

char* infix_to_postfix(char* infix)
{
    int i,a=0;
    char* postfix = malloc(MAX_EQU_LEN);
    stack* s = create_stack();

    for(i=0;infix[i]!='[=10=]';i++){

        if(!isNumeric(&((infix[i]))))
        {
            postfix[a]=infix[i];
            a++;
        }
        else if(isEmpty(s))
            push(s,infix[i]);
        else if(prec(infix[i])>prec(s->stack->data))
                push(s,infix[i]);
        else
            {
                postfix[a]=s->stack->data;
                a++;
                pop(s);
                if(!isEmpty(s)){
                    while(prec(s->stack->data)<= prec (infix[i]))
                    {
                        postfix[a]=s->stack->data;
                        a++;
                        pop(s);
                    }
                }
                else
                    push(s,infix[i]);
            }
        }
    return postfix;

}


int evaluate_postfix(char* postfix) {

    int i,result = 0;
    int right = 0, left = 0;
    char* token = NULL;
    stack* s = create_stack();
    s->size = strlen(postfix);
    node* tempPtr = NULL;
    for(i = 0; i < s->size ; i++)
    {

        token = strtok(postfix, " ");
        if(isNumeric(token) == 1)
        {

            atoi(token);
            push(s, *token);
        }
        else
        {
            left = tempPtr->data;
            pop(s);
            right = tempPtr->data;
            pop(s);
            switch(*token)
            {
                case '+':
                    result = left + right;
                    break;
                case '-':
                    result = left - right;
                    break;
                case '*':
                    result = left * right;
                    break;
                case '/':
                    result = left / right;
                    break;
                case '%':
                    result = left % right;
                    break;

            }
            push(s, result);
        }
        strtok(NULL, " ");
    }
    return result;

}       
#include <stdio.h>
#include <string.h>
#include "calculator.h"

#define BUFFERSIZE 100

int main(int argc, char* argv[]) {

    char buffer[BUFFERSIZE];
    if (argc != 2) {
        printf("correct ussage: %s <input file>\n", argv[0]);
        return 1;
    }

    FILE* fp = fopen(argv[0], "r");

    if(fp == NULL) {
        printf("unable to open file: %s\n", argv[1]);
        return 1;
    }

    while(fgets(buffer, BUFFERSIZE, fp)) {
        if (buffer[strlen(buffer)-1] == '\n') {
            buffer[strlen(buffer)-1] = '[=10=]';
        }
        char *postfix = infix_to_postfix(buffer);
        int result = evaluate_postfix(postfix);
        printf("%s = %d\n", buffer, result);
    }

    return 0;
}

Answer 1

对第一个参数不包含 NULL 指针的 strtok() 的每次调用都会将 strtok() 函数的内部指针重置为字符串的开头。

在 int evaluate_postfix(char* postfix); 函数的循环开始时，您调用

token = strtok(postfix, " ");

这意味着在循环开始时，标记总是指向后缀开头的第一个非space字符。所以每个循环都会看到一个运算符，并尝试从堆栈中弹出（）两个值。但是你的堆栈会很快耗尽，并且堆栈将开始指向垃圾数据 (s->size < 0)。

token = strtok(postfix, " ");

for(i = 0; i < s->size ; i++)
  {
  ....
  token = strtok(NULL, " ");
 }

应该可以解决您的问题。

中缀到后缀

Infix to Postfix

c

stack

infix-notation