c - 后缀在 C 中得到错误的值
问题描述
所以我正在使用链表在 C 中编写一个后缀程序，我的输出值是关闭的，例如表达式：[ 3 4 5 * + 6 7 * 8 + 9 * + ] 应该等于 473，但我的程序返回 4。我还需要检查诸如 (2 3 - where there's no closing ) 之类的错误。现在它忽略它并给我一个价值。
我的代码如下：
#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: %d\n", evaluatePostfix(exp));
return 0;
}
解决方案
对于初学者这个结构定义
// 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;
}
它也不会释放弹出的节点。因此该函数会产生内存泄漏。
相同的问题故事放置在函数 push 声明为
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)
因为传递的字符串在函数中没有改变。
strlen在for循环中使用函数效率低下
for (i = 0; i < strlen(exp); i++)
在函数中，您在每个 case 标签下和 switch 语句之后推送计算结果两次
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: %d\n", evaluatePostfix( exp ) );
return 0;
}
程序输出为
postfix result: 473
您可以在程序中附加一个代码，该代码将检查所传递字符串的当前符号是否为有效符号。那就是传递的表达式是否正确。
推荐阅读
- node.js - 我的电子商务网站出现错误，“'X' is not defined no-undef”
- kubernetes - 为 Minikube Ingress 启用 SSLv3
- .net - 我可以使用 powershell 删除预编译的 .NET C# dll 的清单吗
- java - 使用 Spring Boot 下载 .xls 文件 y Apache POI 不起作用
- ios - UIImageView 圆形 swift
- c# - 嵌套的异步方法太多。那是问题吗？
- python - 如何在 Django 中创建链接以使其他用户无法访问它们？
- azure - 如何在函数应用中引用 Azure Key Vault 中的密钥？
- java - 导入android.support.v4.app.ActivityCompat；
- c - 无法从二进制文件中正确读取结构