编写一个程序实现顺序栈的各种基本运算。1. 初始化顺序栈 2. 插入元素 3. 删除栈顶元素 4. 取栈顶元素 5. 遍历顺序栈 6. 置空顺序栈 7. 实现后缀表达式的运算c语言编写
时间: 2024-10-28 07:09:21 浏览: 35
数据结构顺序栈验证实验报告.pdf
5星 · 资源好评率100%
在C语言中,我们可以按照以下步骤编写一个简单程序来实现顺序栈的各种基本运算,并针对后缀表达式进行计算:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义栈结构体
struct StackNode {
int value;
struct StackNode* next;
};
typedef struct StackNode StackElement;
typedef struct {
StackElement* top;
int size;
} Stack;
// 初始化栈
void createStack(Stack** s) {
*s = (Stack*)malloc(sizeof(Stack));
(*s)->top = NULL;
(*s)->size = 0;
}
// 插入元素到栈顶
void push(Stack** s, int value) {
StackElement* newNode = (StackElement*)malloc(sizeof(StackElement));
newNode->value = value;
newNode->next = (*s)->top;
(*s)->top = newNode;
(*s)->size++;
}
// 删除栈顶元素
void pop(Stack** s) {
if ((*s)->top == NULL) {
printf("Stack is empty.\n");
return;
}
StackElement* temp = (*s)->top;
(*s)->top = (*s)->top->next;
free(temp);
(*s)->size--;
}
// 取栈顶元素
int top(Stack** s) {
if ((*s)->top == NULL) {
printf("Stack is empty.\n");
return -1;
}
return (*s)->top->value;
}
// 遍历栈
void traverse(Stack* s) {
StackElement* current = s->top;
while (current != NULL) {
printf("%d ", current->value);
current = current->next;
}
printf("\n");
}
// 置空栈
void clearStack(Stack** s) {
if (*s == NULL || (*s)->top == NULL) {
printf("Stack is already empty.\n");
return;
}
StackElement* temp = (*s)->top;
while (temp != NULL) {
StackElement* nextTemp = temp->next;
free(temp);
temp = nextTemp;
}
*s = (Stack*)malloc(sizeof(Stack));
(*s)->top = NULL;
(*s)->size = 0;
}
// 后缀表达式运算
int evaluatePostfix(char* postfixExpr) {
Stack* stack = (Stack*)malloc(sizeof(Stack));
createStack(&stack);
for (char* token = strtok(postfixExpr, " ");
token != NULL;
token = strtok(NULL, " ")) {
if (isdigit(*token)) {
push(&stack, *token - '0');
} else {
int secondOperand = top(&stack);
pop(&stack);
int firstOperand = top(&stack);
switch (*token) {
case '+':
push(&stack, firstOperand + secondOperand);
break;
case '-':
push(&stack, firstOperand - secondOperand);
break;
case '*':
push(&stack, firstOperand * secondOperand);
break;
case '/':
push(&stack, firstOperand / secondOperand);
break;
default:
printf("Invalid operator.\n");
clearStack(&stack);
return -1;
}
}
}
if (top(&stack) == -1) {
printf("Invalid expression.\n");
clearStack(&stack);
return -1;
}
int result = top(&stack);
clearStack(&stack);
return result;
}
int main() {
Stack* stack = NULL;
createStack(&stack);
// 插入元素示例
push(&stack, 1);
push(&stack, 2);
push(&stack, 3);
// 打印栈顶元素、遍历栈等操作
printf("Top element: %d\n", top(&stack));
traverse(stack);
// 计算后缀表达式
char* expr = "2 3 + 4 *";
int result = evaluatePostfix(expr);
printf("Result of the postfix expression: %d\n", result);
return 0;
}
```
阅读全文