c语言中缀表达式转后缀表达式的代码
时间: 2023-12-25 11:28:57 浏览: 40
以下是C语言实现中缀表达式转后缀表达式的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SIZE 100
typedef struct {
char data[MAX_SIZE];
int top;
} Stack;
void initStack(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, char c) {
if (isFull(s)) {
printf("Stack is full.\n");
exit(1);
}
s->data[++s->top] = c;
}
char pop(Stack *s) {
if (isEmpty(s)) {
printf("Stack is empty.\n");
exit(1);
}
return s->data[s->top--];
}
int isOperator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/';
}
int precedence(char c) {
if (c == '+' || c == '-')
return 1;
else if (c == '*' || c == '/')
return 2;
else
return 0;
}
void infixToPostfix(char *infix, char *postfix) {
Stack s;
initStack(&s);
int i, j;
char c;
for (i = 0, j = 0; infix[i] != '\0'; i++) {
if (infix[i] == ' ')
continue;
else if (isdigit(infix[i]) || isalpha(infix[i])) {
postfix[j++] = infix[i];
} else if (infix[i] == '(') {
push(&s, infix[i]);
} else if (infix[i] == ')') {
while ((c = pop(&s)) != '(')
postfix[j++] = c;
} else if (isOperator(infix[i])) {
while (!isEmpty(&s) && precedence(infix[i]) <= precedence(s.data[s.top]))
postfix[j++] = pop(&s);
push(&s, infix[i]);
} else {
printf("Invalid character: %c\n", infix[i]);
exit(1);
}
}
while (!isEmpty(&s))
postfix[j++] = pop(&s);
postfix[j] = '\0';
}
int evaluatePostfix(char *postfix) {
Stack s;
initStack(&s);
int i, operand1, operand2, result;
for (i = 0; postfix[i] != '\0'; i++) {
if (isdigit(postfix[i])) {
push(&s, postfix[i] - '0');
} else if (isOperator(postfix[i])) {
operand2 = pop(&s);
operand1 = pop(&s);
switch (postfix[i]) {
case '+':
result = operand1 + operand2;
break;
case '-':
result = operand1 - operand2;
break;
case '*':
result = operand1 * operand2;
break;
case '/':
result = operand1 / operand2;
break;
}
push(&s, result);
}
}
return pop(&s);
}
int main() {
char infix[MAX_SIZE];
char postfix[MAX_SIZE];
printf("Enter an infix expression: ");
fgets(infix, MAX_SIZE, stdin);
infix[strlen(infix) - 1] = '\0';
infixToPostfix(infix, postfix);
printf("Postfix expression: %s\n", postfix);
int result = evaluatePostfix(postfix);
printf("Result: %d\n", result);
return 0;
}
```