用栈实现带括号的四则运算 C语言
时间: 2023-12-27 22:04:58 浏览: 37
以下是用栈实现带括号的四则运算的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
typedef struct {
int top;
int data[MAX_SIZE];
} Stack;
void init(Stack *s) {
s->top = -1;
}
int is_empty(Stack *s) {
return s->top == -1;
}
int is_full(Stack *s) {
return s->top == MAX_SIZE - 1;
}
void push(Stack *s, int x) {
if (is_full(s)) {
printf("Error: stack is full\n");
exit(-1);
}
s->data[++s->top] = x;
}
int pop(Stack *s) {
if (is_empty(s)) {
printf("Error: stack is empty\n");
exit(-1);
}
return s->data[s->top--];
}
int peek(Stack *s) {
if (is_empty(s)) {
printf("Error: stack is empty\n");
exit(-1);
}
return s->data[s->top];
}
int is_digit(char c) {
return c >= '0' && c <= '9';
}
int is_operator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/';
}
int priority(char op) {
if (op == '*' || op == '/') {
return 2;
} else if (op == '+' || op == '-') {
return 1;
} else {
return 0;
}
}
int calculate(int a, char op, int b) {
switch (op) {
case '+':
return a + b;
case '-':
return a - b;
case '*':
return a * b;
case '/':
return a / b;
default:
printf("Error: unsupported operator %c\n", op);
exit(-1);
}
}
int evaluate(char *expr) {
Stack operand_stack, operator_stack;
init(&operand_stack);
init(&operator_stack);
int i = 0;
while (expr[i] != '\0') {
if (expr[i] == '(') {
push(&operator_stack, '(');
} else if (is_digit(expr[i])) {
int num = 0;
while (is_digit(expr[i])) {
num = num * 10 + (expr[i] - '0');
i++;
}
push(&operand_stack, num);
i--;
} else if (is_operator(expr[i])) {
while (!is_empty(&operator_stack) && peek(&operator_stack) != '(' &&
priority(expr[i]) <= priority(peek(&operator_stack))) {
int b = pop(&operand_stack);
int a = pop(&operand_stack);
char op = pop(&operator_stack);
push(&operand_stack, calculate(a, op, b));
}
push(&operator_stack, expr[i]);
} else if (expr[i] == ')') {
while (!is_empty(&operator_stack) && peek(&operator_stack) != '(') {
int b = pop(&operand_stack);
int a = pop(&operand_stack);
char op = pop(&operator_stack);
push(&operand_stack, calculate(a, op, b));
}
pop(&operator_stack);
}
i++;
}
while (!is_empty(&operator_stack)) {
int b = pop(&operand_stack);
int a = pop(&operand_stack);
char op = pop(&operator_stack);
push(&operand_stack, calculate(a, op, b));
}
return pop(&operand_stack);
}
int main() {
char expr[MAX_SIZE];
printf("Enter an expression: ");
fgets(expr, MAX_SIZE, stdin);
printf("Result: %d\n", evaluate(expr));
return 0;
}
```
程序首先定义了一个栈结构体,包括栈顶指针和数据数组。然后定义了一些基本栈操作函数,如初始化栈、判断栈是否为空、判断栈是否已满、入栈、出栈和查看栈顶元素等。
接下来定义了一些辅助函数,如判断字符是否为数字、判断字符是否为运算符、获取运算符的优先级和计算两个操作数之间的结果。
最后实现了主函数,该函数接收用户输入的表达式,并使用栈来计算表达式的值。程序遍历输入的表达式中的每个字符,如果遇到左括号,则将其压入运算符栈中。如果遇到数字,则将其解析为整数并压入操作数栈中。如果遇到运算符,则将该运算符与运算符栈中的运算符进行比较,如果该运算符的优先级不高于栈顶运算符,则将栈顶运算符弹出,从操作数栈中弹出两个操作数进行运算,并将结果压入操作数栈中。如果遇到右括号,则弹出运算符栈中的运算符,并从操作数栈中弹出两个操作数进行运算,并将结果压入操作数栈中。最后,如果运算符栈不为空,则继续弹出栈顶运算符,并从操作数栈中弹出两个操作数进行运算,直到最终得到表达式的结果。
相关推荐
![](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)