用c语言实现计算中缀表达式
时间: 2023-11-28 09:06:33 浏览: 76
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SIZE 100
typedef struct {
int data[MAX_SIZE];
int top;
} Stack;
void init(Stack *s) {
s->top = -1;
}
int isEmpty(Stack *s) {
return s->top == -1;
}
int isFull(Stack *s) {
return s->top == MAX_SIZE - 1;
}
void push(Stack *s, int x) {
if (isFull(s)) {
printf("Stack overflow\n");
exit(1);
}
s->data[++s->top] = x;
}
int pop(Stack *s) {
if (isEmpty(s)) {
printf("Stack underflow\n");
exit(1);
}
return s->data[s->top--];
}
int peek(Stack *s) {
if (isEmpty(s)) {
printf("Stack underflow\n");
exit(1);
}
return s->data[s->top];
}
int isOperator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/';
}
int precedence(char op) {
if (op == '+' || op == '-') {
return 1;
} else if (op == '*' || op == '/') {
return 2;
}
return 0;
}
int evaluate(int a, int b, char op) {
switch (op) {
case '+':
return a + b;
case '-':
return a - b;
case '*':
return a * b;
case '/':
return a / b;
}
return 0;
}
int evaluatePostfix(char *expr) {
Stack s;
init(&s);
int len = strlen(expr);
for (int i = 0; i < len; i++) {
if (expr[i] == ' ') {
continue;
} else if (isdigit(expr[i])) {
int num = 0;
while (isdigit(expr[i])) {
num = num * 10 + (expr[i] - '0');
i++;
}
i--;
push(&s, num);
} else if (isOperator(expr[i])) {
int b = pop(&s);
int a = pop(&s);
int result = evaluate(a, b, expr[i]);
push(&s, result);
}
}
return pop(&s);
}
int evaluateInfix(char *expr) {
Stack s;
init(&s);
int len = strlen(expr);
for (int i = 0; i < len; i++) {
if (expr[i] == ' ') {
continue;
} else if (isdigit(expr[i])) {
int num = 0;
while (isdigit(expr[i])) {
num = num * 10 + (expr[i] - '0');
i++;
}
i--;
push(&s, num);
} else if (expr[i] == '(') {
push(&s, '(');
} else if (expr[i] == ')') {
while (peek(&s) != '(') {
int b = pop(&s);
int a = pop(&s);
char op = pop(&s);
int result = evaluate(a, b, op);
push(&s, result);
}
pop(&s);
} else if (isOperator(expr[i])) {
while (!isEmpty(&s) && precedence(peek(&s)) >= precedence(expr[i])) {
int b = pop(&s);
int a = pop(&s);
char op = pop(&s);
int result = evaluate(a, b, op);
push(&s, result);
}
push(&s, expr[i]);
}
}
while (!isEmpty(&s)) {
int b = pop(&s);
int a = pop(&s);
char op = pop(&s);
int result = evaluate(a, b, op);
push(&s, result);
}
return pop(&s);
}
int main() {
char expr[MAX_SIZE];
printf("Enter an infix expression: ");
fgets(expr, MAX_SIZE, stdin);
int result = evaluateInfix(expr);
printf("Result: %d\n", result);
return 0;
}
阅读全文