用C语言数据结构实现【样例输入】 4 Add 1 Sub 2 Mul 4 Sub 4 5 【样例输出】 3 【样例说明】 计算表达式为(5-4)*4-2+1并给出详细注释
时间: 2024-06-01 10:11:33 浏览: 28
#include <stdio.h>
#include <stdlib.h>
// 定义栈结构体
typedef struct {
int *data; // 存储数据的指针
int top; // 栈顶指针
int size; // 栈的大小
} Stack;
// 初始化栈
void initStack(Stack *s, int size) {
s->data = (int *)malloc(size * sizeof(int));
s->top = -1;
s->size = size;
}
// 判断栈是否为空
int isEmpty(Stack *s) {
return s->top == -1;
}
// 判断栈是否已满
int isFull(Stack *s) {
return s->top == s->size - 1;
}
// 入栈
void push(Stack *s, int value) {
if (isFull(s)) {
printf("Error: stack is full!\n");
return;
}
s->top++;
s->data[s->top] = value;
}
// 出栈
int pop(Stack *s) {
if (isEmpty(s)) {
printf("Error: stack is empty!\n");
return -1;
}
int value = s->data[s->top];
s->top--;
return value;
}
// 获取栈顶元素
int getTop(Stack *s) {
if (isEmpty(s)) {
printf("Error: stack is empty!\n");
return -1;
}
return s->data[s->top];
}
// 计算表达式的值
int calculate(int a, int b, char op) {
switch (op) {
case '+':
return a + b;
case '-':
return a - b;
case '*':
return a * b;
case '/':
return a / b;
default:
printf("Error: invalid operator!\n");
return 0;
}
}
int main() {
int n;
scanf("%d", &n);
char op[4]; // 操作符
int num; // 操作数
Stack numStack, opStack; // 数字栈和操作符栈
initStack(&numStack, n);
initStack(&opStack, n);
for (int i = 0; i < n; i++) {
scanf("%s %d", op, &num);
if (op[0] == 'A') { // 加法直接入操作符栈
push(&opStack, '+');
} else if (op[0] == 'S') { // 减法直接入操作符栈
push(&opStack, '-');
} else if (op[0] == 'M') { // 乘法先计算前面的乘法
while (!isEmpty(&opStack) && getTop(&opStack) == '*') {
int b = pop(&numStack);
int a = pop(&numStack);
char op = pop(&opStack);
int result = calculate(a, b, op);
push(&numStack, result);
}
push(&opStack, '*'); // 再入操作符栈
} else if (op[0] == 'D') { // 除法同乘法
while (!isEmpty(&opStack) && getTop(&opStack) == '/') {
int b = pop(&numStack);
int a = pop(&numStack);
char op = pop(&opStack);
int result = calculate(a, b, op);
push(&numStack, result);
}
push(&opStack, '/');
}
push(&numStack, num); // 操作数入数字栈
}
// 计算剩余的乘除法
while (!isEmpty(&opStack)) {
int b = pop(&numStack);
int a = pop(&numStack);
char op = pop(&opStack);
int result = calculate(a, b, op);
push(&numStack, result);
}
printf("%d\n", pop(&numStack)); // 最终结果即为数字栈中仅剩的元素
return 0;
}
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)