#include <stdio.h>
#include <stdlib.h>
int LENGTH = 1;
int TOP = -1;
void push(char**, char);
char pop(char*);
char peek(char*);
int isEmpty();
int isFull();
void convertToRPN(char*, char*, char*);
int isOperator(char);
int getPrecedence(char);
int main(void) {
char* stack = (char*) malloc(sizeof(char) * LENGTH);
if (!stack) {
printf("Memory allocation failed./n");
exit(1);
}
char expression[100];
printf("Enter the mathematical expression: ");
scanf("%s", expression);
char rpn[100];
convertToRPN(expression, stack, rpn);
printf("The rpn: %s\n", rpn);
free(stack);
return 0;
}
int isOperator(char c) {
return (c == '+' || c == '-' || c == '*' || c == '/');
}
int getPrecedence(char c) {
if (c == '+' || c == '-')
return 1;
if (c == '*' || c == '/')
return 2;
return 0;
}
void convertToRPN(char *expression, char* stack, char* rpn) {
int j = 0;
for (int i = 0; expression[i] != '\0'; i++) {
if (expression[i] >= '0' && expression[i] <= '9') {
rpn[j] = expression[i];
j++;
} else if (isOperator(expression[i])) {
while (!isEmpty() && peek(stack) != '(' && getPrecedence(peek(stack)) >= getPrecedence(expression[i])) {
rpn[j] = pop(stack);
j++;
}
push(&stack, expression[i]);
} else if (expression[i] == '(') {
push(&stack, expression[i]);
} else if (expression[i] == ')') {
while (!isEmpty() && peek(stack) != '(') {
rpn[j] = pop(stack);
j++;
}
pop(stack);
} else {
printf("Unsupported character.\n");
exit(2);
}
}
while (!isEmpty()) {
rpn[j] = pop(stack);
j++;
}
rpn[j] = '\0';
}
void push(char **stack, char c) {
if (isFull()) {
*stack = (char *)realloc(*stack, sizeof(char) * (LENGTH + 1));
if (!*stack) {
printf("Memory reallocation failed.\n");
exit(5);
}
LENGTH++;
}
TOP++;
(*stack)[TOP] = c;
}
char pop(char *stack) {
if (isEmpty()) {
printf("POP: the stack is empty.\n");
exit(3);
} else {
char item = stack[TOP];
TOP--;
return item;
}
}
char peek(char *stack) {
if (isEmpty()) {
printf("PEEK: the stack is empty.\n");
exit(4);
}
return stack[TOP];
}
int isEmpty() {
return TOP == -1;
}
int isFull() {
return TOP == LENGTH - 1;
}
This code performs RPN (Reverse Polish notation) conversion, but gives definite lost in 1 block. According to valgrind the code has a memory leak issue.The message is cryptic, but I guess it's in realloc(). Maybe to help the message:
Enter the mathematical expression: 5+9+21 The rpn: 59+21+
Invalid free() / delete / delete[] / realloc() at 0x484810F: free by 0x1092FE: main (exer1_2.c:34) Address 0x4a78040 is 0 bytes inside a block of size 1 free'd at 0x484ABC0: realloc by 0x109616: push (exer1_2.c:92) by 0x1094BB: convertToRPN by 0x1092D4: main Block was alloc'd at at 0x4845828: malloc by 0x109256: main
HEAP SUMMARY: in use at exit: 2 bytes in 1 blocks total heap usage: 4 allocs, 4 frees, 2,051 bytes allocated
LEAK SUMMARY: definitely lost: 2 bytes in 1 blocks indirectly lost: 0 bytes in 0 blocks possibly lost: 0 bytes in 0 blocks still reachable: 0 bytes in 0 blocks suppressed: 0 bytes in 0 blocks
ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)
Overall i guess the problem is about my implementation of the stack.
There is a bug in the program. The pointer stack
is passed to the function convertToRPN
by value
void convertToRPN(char*, char*, char*);
//...
convertToRPN(expression, stack, rpn);
So the function deals with a copy of the value of the original pointer. The original pointer stays unchanged. As a result the pointer has an invalid value and this call of free
in main
free(stack);
does not free the memory allocated during execution of the function convertToRPN
.
You should at least pass the pointer by reference to the function through a pointer to it. That is the function should be declared and called like
void convertToRPN(char*, char**, char*);
//...
convertToRPN(expression, &stack, rpn);
though it would be better if neither memory for the stack was allocated in main
. The stack is used in the function convertToRPN
where memory should be allocated and freed.
And it would be better to declare a structure Stack like for example
struct Stack
{
size_t top;
size_t size;
char *mem;
};
and use an object of the structure instead of several separate variables. And it is a very bad idea to use global variables
int LENGTH = 1;
int TOP = -1;
I advise you to redesign the code.