写一段C语言程序,将输入的中缀表达式转化为后缀表达式并且可以求值,要求1.程序可以识别多位整数,小数2.对你输入的中缀表达式进行判断是否正确,正确则进行转换与求值,不正确则进行报错,指出错误所在
时间: 2024-03-15 18:44:01 浏览: 127
好的,以下是这个程序的实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <string.h>
#define STACK_SIZE 100
#define QUEUE_SIZE 100
typedef struct {
double data[STACK_SIZE];
int top;
} Stack;
typedef struct {
char data[QUEUE_SIZE];
int front, rear;
} Queue;
void init_stack(Stack *s) {
s->top = -1;
}
void push(Stack *s, double x) {
if (s->top == STACK_SIZE - 1) {
printf("Error: Stack overflow!\n");
exit(1);
}
s->top++;
s->data[s->top] = x;
}
double pop(Stack *s) {
if (s->top == -1) {
printf("Error: Stack is empty!\n");
exit(1);
}
double x = s->data[s->top];
s->top--;
return x;
}
double top(Stack *s) {
if (s->top == -1) {
printf("Error: Stack is empty!\n");
exit(1);
}
return s->data[s->top];
}
int is_empty(Stack *s) {
return s->top == -1;
}
int is_full(Stack *s) {
return s->top == STACK_SIZE - 1;
}
void init_queue(Queue *q) {
q->front = q->rear = 0;
}
void enqueue(Queue *q, char x) {
if ((q->rear + 1) % QUEUE_SIZE == q->front) {
printf("Error: Queue overflow!\n");
exit(1);
}
q->data[q->rear] = x;
q->rear = (q->rear + 1) % QUEUE_SIZE;
}
char dequeue(Queue *q) {
if (q->front == q->rear) {
printf("Error: Queue is empty!\n");
exit(1);
}
char x = q->data[q->front];
q->front = (q->front + 1) % QUEUE_SIZE;
return x;
}
char front(Queue *q) {
if (q->front == q->rear) {
printf("Error: Queue is empty!\n");
exit(1);
}
return q->data[q->front];
}
int is_queue_empty(Queue *q) {
return q->front == q->rear;
}
int is_queue_full(Queue *q) {
return (q->rear + 1) % QUEUE_SIZE == q->front;
}
int priority(char op) {
if (op == '+' || op == '-')
return 1;
else if (op == '*' || op == '/')
return 2;
else if (op == '^')
return 3;
else
return 0;
}
void infix_to_postfix(char *infix, char *postfix) {
Stack s;
init_stack(&s);
int i = 0, j = 0;
while (infix[i] != '\0') {
if (isdigit(infix[i])) {
postfix[j++] = infix[i++];
while (isdigit(infix[i]) || infix[i] == '.') {
postfix[j++] = infix[i++];
}
postfix[j++] = ' ';
}
else if (infix[i] == '(') {
push(&s, infix[i++]);
}
else if (infix[i] == ')') {
while (top(&s) != '(') {
postfix[j++] = pop(&s);
}
pop(&s);
i++;
}
else if (infix[i] == '+' || infix[i] == '-' || infix[i] == '*' || infix[i] == '/' || infix[i] == '^') {
while (!is_empty(&s) && top(&s) != '(' && priority(top(&s)) >= priority(infix[i])) {
postfix[j++] = pop(&s);
}
push(&s, infix[i++]);
}
else {
printf("Error: Invalid character!\n");
exit(1);
}
}
while (!is_empty(&s)) {
if (top(&s) == '(') {
printf("Error: Mismatched parentheses!\n");
exit(1);
}
postfix[j++] = pop(&s);
}
postfix[j] = '\0';
}
double evaluate_postfix(char *postfix) {
Stack s;
init_stack(&s);
int i = 0;
while (postfix[i] != '\0') {
if (isdigit(postfix[i])) {
double x = 0;
while (isdigit(postfix[i])) {
x = x * 10 + postfix[i] - '0';
i++;
}
if (postfix[i] == '.') {
i++;
double k = 0.1;
while (isdigit(postfix[i])) {
x += k * (postfix[i] - '0');
k *= 0.1;
i++;
}
}
push(&s, x);
}
else if (postfix[i] == ' ') {
i++;
}
else {
double x = pop(&s);
double y = pop(&s);
switch (postfix[i]) {
case '+': push(&s, y + x); break;
case '-': push(&s, y - x); break;
case '*': push(&s, y * x); break;
case '/': push(&s, y / x); break;
case '^': push(&s, pow(y, x)); break;
default: printf("Error: Invalid operator!\n"); exit(1);
}
i++;
}
}
return pop(&s);
}
int is_valid_infix(char *infix) {
Stack s;
init_stack(&s);
int i = 0;
while (infix[i] != '\0') {
if (isdigit(infix[i])) {
i++;
while (isdigit(infix[i]) || infix[i] == '.') {
i++;
}
}
else if (infix[i] == '(') {
push(&s, '(');
i++;
}
else if (infix[i] == ')') {
if (is_empty(&s)) {
return 0;
}
pop(&s);
i++;
}
else if (infix[i] == '+' || infix[i] == '-' || infix[i] == '*' || infix[i] == '/' || infix[i] == '^') {
if (is_empty(&s) || top(&s) == '(' || priority(top(&s)) < priority(infix[i])) {
return 0;
}
i++;
}
else {
return 0;
}
}
return is_empty(&s);
}
int main() {
char infix[STACK_SIZE], postfix[STACK_SIZE];
printf("Enter an infix expression: ");
fgets(infix, STACK_SIZE, stdin);
if (infix[strlen(infix)-1] == '\n') {
infix[strlen(infix)-1] = '\0';
}
if (!is_valid_infix(infix)) {
printf("Error: Invalid infix expression!\n");
exit(1);
}
infix_to_postfix(infix, postfix);
printf("Postfix expression: %s\n", postfix);
double result = evaluate_postfix(postfix);
printf("Result: %g\n", result);
return 0;
}
```
这个程序实现了中缀表达式转换为后缀表达式并求值的功能,同时还进行了错误检查,如果输入的中缀表达式不合法,就会报错并退出程序。
阅读全文