#c #string #data-structures #stack #prefix-notation
#c #строка #структуры данных #стек #префикс-обозначение
Вопрос:
Ниже приведен код для преобразования инфикса в префикс. Мой код работает нормально до тех пор, пока не будет использована reverse
функция, в которой он не печатает ни одной строки после копирования. Я попытался использовать for
цикл для копирования перевернутой строки, но результат остается тем же, и программа завершается без надлежащего вывода. Инструкции печати в reverse
функции работают до копирования, но не после этого. Кто-нибудь может сообщить мне, в чем проблема?
#includelt;stdio.hgt; #includelt;stdlib.hgt; #includelt;string.hgt; struct stack{ int size; int top; char *arr; }; void display(struct stack *ptr) { if(ptr-gt;top == -1) { printf("Stack is Empty"); } else { for(int i = ptr-gt;top ; igt;=0 ; i--) { printf("Element: %dn",ptr-gt;arr[i]); } } } int isEmpty(struct stack *ptr) { if(ptr-gt;top == -1) { return 1; } else { return 0; } } int isFull(struct stack *ptr) { if(ptr-gt;top == ptr-gt;size - 1) { return 1; } else { return 0; } } void push(struct stack *ptr,int data) { if(isFull(ptr)) { printf("Stack Overflow"); } else { ptr-gt;top = ptr-gt;top 1; ptr-gt;arr[ptr-gt;top] = data; } } char pop(struct stack *ptr) { if(isEmpty(ptr)) { printf("Stack Underflow"); return 0; } else { char ch = ptr-gt;arr[ptr-gt;top]; ptr-gt;top = ptr-gt;top - 1; return ch; } } char stackTop(struct stack *ptr) { return ptr-gt;arr[ptr-gt;top]; } int isOperator(char a) { if(a == ' '|| a == '-'|| a == '*'|| a == '/') { return 1; } else { return 0; } } int precedence(char a) { if(a == '*' || a == '/') { return 3; } else if(a == ' ' || a == '-') { return 2; } else { return -1; } } char * reverse(char exp[]) { int l = strlen(exp); int j = 0; char temp[l]; for(int i=l-1;igt;=0;i--,j ) { temp[j] = exp[i]; } temp[j] = ''; printf("prefix is %s",temp); strcpy(exp,temp); // for(int i=0;ilt;=l;i ) // { // exp[i] = temp[i]; // } printf("prefix is %s",exp); return exp; } char * infix_prefix(char *infix) { struct stack *sp = (struct stack *) malloc(sizeof(struct stack)); sp-gt;size = 100; sp-gt;top = -1; sp-gt;arr = (char *) malloc(sp-gt;size * sizeof(char)); char *prefix = (char *) malloc((strlen(infix 1)) * sizeof(char)); infix = reverse(infix); int i=0; int j=0; while(infix[i] != '') { if(infix[i] == ')') { push(sp,infix[i]); i ; } else if(infix[i] == '(') { while(!isEmpty(sp) amp;amp; stackTop(sp) != ')') { prefix[j] = pop(sp); j ; } if(!isEmpty(sp)) { pop(sp); i ; } else { printf("Incorrect Expression"); exit(0); } } else if(!isOperator(infix[i])) { prefix[j] = infix[i]; i ; j ; } else if(isOperator(infix[i])) { while(!isEmpty(sp) amp;amp; precedence(infix[i])lt;=precedence(stackTop(sp))) { prefix[j] = pop(sp); j ; } push(sp,infix[i]); i ; } else { printf("Incorrect expression"); exit(0); } } while(!isEmpty(sp) amp;amp; stackTop(sp) != '(') { prefix[j] = pop(sp); j ; } if(stackTop(sp) == ')') { printf("Incorrect expression"); exit(0); } prefix = reverse(prefix); prefix[j] = ''; return prefix; } int main(void) { char *infix = "(x-y/z-k*d)"; printf("prefix is %s",infix_prefix(infix)); return 0; }
Комментарии:
1. компилировался ли он вообще, если он был скомпилирован, то получил ли какое-либо предупреждение или ошибку во время выполнения, или вы получили ошибку компиляции?
2. К вашему сведению, это буквально то, для чего создан отладчик. Я бы начал с того, что понял, что строка, на которую указывает
infix
inmain
, неизменна, но вы все равно наступаете на нееreverse
. Изменениеchar *infix
наchar infix[]
, вероятно, продвинет вас дальше, чем вы сейчас.
Ответ №1:
У reverse
действительно есть проблема: temp
массив определен длиной l
: этого недостаточно для хранения нулевого терминатора temp[j]
после цикла, что приводит к неопределенному поведению.
Есть и другие проблемы:
char *prefix = (char *) malloc((strlen(infix 1)) * sizeof(char));
не выделяет достаточно места для копииinfix
. Тебе следует написатьchar *prefix = malloc(strlen(infix) 1);
infix = reverse(infix);
произойдет сбой, потому что аргумент toinfix_prefix
является строковым литералом, который не должен быть изменен. Вы должны объявить аргумент какconst char *infix
и сделать изменяемую копию сstrdup()
помощью, если реверсирование действительно необходимо, в чем я очень сомневаюсь.
Вот модифицированная версия reverse
, которая выполняет обратную операцию на месте:
char *reverse(char exp[]) { int i = 0; int j = strlen(exp); while (j-- gt; i) { char c = exp[j]; exp[j] = exp[i]; exp[i ] = c; } return exp; }
Комментарии:
1. Спасибо за ответ, я изменил метод выделения памяти для каждого массива и дал ему определенный размер, достаточный для работы программы, и теперь программа работает нормально.