Postfix在C中得到错误的值

Question

所以我用链表在C中写一个后缀程序，我的输出值是off，例如表达式：[3 4 5*+6 7*8+9*+]应该等于473，但我的程序返回4。我还需要检查错误，例如(23-没有结束的地方(。现在它忽略了它，给了我一个值。

我的代码如下：

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>
// Node to store data and address of next next
struct Node
{
int value;
struct Node *next;
} ;
// Stack type
typedef struct Stack
{
int value;
struct Node* top;
struct Node* back;
} Stack;
// Stack Operations
struct Stack* createStack()
{
Stack* stack = (Stack*) malloc(sizeof(Stack));
if (!stack)
return NULL;
stack->top = NULL;
stack->value = 0;
return stack;
}
// check stack is empty or not
int isEmpty(Stack* stack)
{
return stack->top == NULL;
}
// return peek of stack
int peek(Stack* stack)
{
return stack->top->value;
}
/**
* return top of stack and pop element from top of stack
*/
int pop(Stack* stack)
{
char  top;
if (!isEmpty(stack)) // no empty
{
top = stack->top->value;
stack->top = stack->top->next;
stack->value--;
return top;
}
return -1;
}
/*
* push an element into stack
*/
void push(Stack* stack, char  op)
{
struct Node *newNode = (struct Node*) malloc(sizeof(struct Node*));
newNode->next = NULL;
newNode->value = op;
if (isEmpty(stack))
{
stack->top = newNode;
stack->value++;
return;
}
newNode->next = stack->top;
stack->top = newNode;
}

// The main function that returns value of a given postfix expression
int evaluatePostfix(char* exp)
{
// Create a stack of capacity equal to expression size
Stack* stack = createStack();
int i, val, val2, res;
// Scan all characters one by one
for (i = 0; i < strlen(exp); i++)
{
// If the scanned character is an operand (number here),
// push it to the stack.
if (isdigit(exp[i]))
push(stack, exp[i] - '0');

// If the scanned character is an operator, pop two
// elements from stack apply the operator
else
{
val = pop(stack);
val2 = pop(stack);
switch (exp[i])
{
case '+':
res = val2 + val;
push(stack, res);
break;
case '-':
res = val2 - val;
push(stack, res);
break;
case '*':
res = val2 * val;
push(stack, res);
break;
case '/':
res = val2 / val;
push(stack, res);
break;
}
push (stack, res);
}
}
return pop(stack);
}
// Driver program to test above functions
int main()
{
char exp [20];
Stack* stack = createStack();

printf("Enter postfix expression: ");
scanf("%s", exp);

printf ("postfix result: %dn", evaluatePostfix(exp));
return 0;
}

Answer 1

对于初学者来说，这个结构定义

// Stack type
typedef struct Stack
{
int value;
struct Node* top;
struct Node* back;
} Stack;

没有多大意义。例如，不使用数据成员back。数据成员value的含义是未知的。

动态定义Stack类型的对象是没有意义的。所以这个功能

struct Stack* createStack()
{
Stack* stack = (Stack*) malloc(sizeof(Stack));
if (!stack)
return NULL;
stack->top = NULL;
stack->value = 0;
return stack;
}

是多余的。

函数pop使用类型为char而不是int的对象来返回存储在堆栈中的值。类型为char的对象不能存储等于例如473的正值。

/**
* return top of stack and pop element from top of stack
*/
int pop(Stack* stack)
{
char  top;
^^^^^^^^^^
if (!isEmpty(stack)) // no empty
{
top = stack->top->value;
stack->top = stack->top->next;
stack->value--;
return top;
}
return -1;
}

此外，它不会释放弹出的节点。因此该函数会产生内存泄漏。

在像一样声明的功能推送中放置相同的问题信号

void push(Stack* stack, char  op);
^^^^^^^^^

此外，当堆栈不为空时，您忘记增加数据成员value。

if (isEmpty(stack))
{
stack->top = newNode;
stack->value++;
return;
}
newNode->next = stack->top;
stack->top = newNode;
// stack->value++; <===

函数evaluatePostfix应具有带参数的限定符const

int evaluatePostfix( const char* exp)

因为传递的字符串在函数中没有更改。

在for循环中使用函数strlen是低效的

for (i = 0; i < strlen(exp); i++)

在函数中，您在每个案例标签下和切换语句之后推送两次计算结果

switch (exp[i])
{
case '+':
res = val2 + val;
push(stack, res);
break;
case '-':
res = val2 - val;
push(stack, res);
break;
case '*':
res = val2 * val;
push(stack, res);
break;
case '/':
res = val2 / val;
push(stack, res);
break;
}
push (stack, res); 

最好跳过字符串中嵌入的空白。

由于堆栈是动态分配的，您需要在退出函数之前释放它。

下面是一个演示程序，展示了如何编写该程序。

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
typedef struct Stack
{
struct Node
{
int value;
struct Node *next;
} *top;
} Stack;
int push( Stack* stack, int  value )
{
struct Node *newNode = malloc( sizeof( struct Node ) );
int success = newNode != NULL;

if ( success )
{
newNode->value = value;
newNode->next = stack->top;

stack->top = newNode;
}

return success;
}
void pop( Stack *stack )
{
if ( stack->top != NULL )
{
struct Node *tmp = stack->top;
stack->top = stack->top->next;
free( tmp );
}
}
int isEmpty( Stack *stack )
{
return stack->top == NULL;
}
int peek( Stack *stack )
{
return stack->top->value;
}

// The main function that returns value of a given postfix expression
int evaluatePostfix( const char *exp )
{
// Create a stack of capacity equal to expression size
Stack stack = { NULL };
int res = 0;
// Scan all characters one by one
for ( ; *exp; ++exp )
{
if ( !isspace( ( unsigned char )*exp ) )
{
// If the scanned character is an operand (number here),
// push it to the stack.
if ( isdigit( ( unsigned char ) *exp ) )
{
push( &stack, *exp - '0' );
}
// If the scanned character is an operator, pop two
// elements from stack apply the operator
else
{
int val = peek( &stack );
pop( &stack );
int val2 = peek( &stack );
pop( &stack );
res = 0;
switch ( *exp )
{
case '+':
res = val2 + val;
break;
case '-':
res = val2 - val;
break;
case '*':
res = val2 * val;
break;
case '/':
res = val2 / val;
break;
}

push( &stack, res );
}
}
}

if ( !isEmpty( &stack ) ) 
{
res = peek( &stack );
pop( &stack );
}

return res;
}
int main(void) 
{
const char *exp = "3 4 5 * + 6 7 * 8 + 9 * +";

printf( "postfix result: %dn", evaluatePostfix( exp ) );

return 0;
}

程序输出为

postfix result: 473

您可以在程序中附加一个代码，检查传递字符串的当前符号是否为有效符号。这就是传递的表达式是否正确。