设计一个算法,将一般算术表达式转化为逆波兰表达式,并求逆波兰表达 式的值C语言
时间: 2023-04-04 13:00:48 浏览: 286
我可以回答这个问题。将一般算术表达式转化为逆波兰表达式的算法可以使用栈来实现。具体步骤如下:
1. 创建一个栈,用于存储运算符和操作数。
2. 从左到右扫描表达式的每个元素,如果是操作数,则将其压入栈中。
3. 如果是运算符,则弹出栈顶的两个操作数,进行运算,并将结果压入栈中。
4. 重复步骤2和3,直到扫描完整个表达式。
5. 最后栈中只剩下一个元素,即为逆波兰表达式的值。
以下是一个示例代码:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAX_SIZE 100
typedef struct {
int top;
int data[MAX_SIZE];
} Stack;
void init(Stack *s) {
s->top = -1;
}
void push(Stack *s, int x) {
if (s->top == MAX_SIZE - 1) {
printf("Stack overflow\n");
exit(1);
}
s->data[++s->top] = x;
}
int pop(Stack *s) {
if (s->top == -1) {
printf("Stack underflow\n");
exit(1);
}
return s->data[s->top--];
}
int is_operator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/';
}
int precedence(char c) {
switch (c) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
default:
return ;
}
}
void infix_to_postfix(char *infix, char *postfix) {
Stack s;
init(&s);
int i = , j = ;
while (infix[i] != '\') {
if (isdigit(infix[i])) {
postfix[j++] = infix[i++];
while (isdigit(infix[i])) {
postfix[j++] = infix[i++];
}
postfix[j++] = ' ';
} else if (is_operator(infix[i])) {
while (s.top != -1 && is_operator(s.data[s.top]) && precedence(s.data[s.top]) >= precedence(infix[i])) {
postfix[j++] = pop(&s);
postfix[j++] = ' ';
}
push(&s, infix[i++]);
} else if (infix[i] == '(') {
push(&s, infix[i++]);
} else if (infix[i] == ')') {
while (s.top != -1 && s.data[s.top] != '(') {
postfix[j++] = pop(&s);
postfix[j++] = ' ';
}
if (s.top == -1) {
printf("Mismatched parentheses\n");
exit(1);
}
pop(&s);
i++;
} else if (isspace(infix[i])) {
i++;
} else {
printf("Invalid character: %c\n", infix[i]);
exit(1);
}
}
while (s.top != -1) {
if (s.data[s.top] == '(') {
printf("Mismatched parentheses\n");
exit(1);
}
postfix[j++] = pop(&s);
postfix[j++] = ' ';
}
postfix[j] = '\';
}
int evaluate_postfix(char *postfix) {
Stack s;
init(&s);
int i = ;
while (postfix[i] != '\') {
if (isdigit(postfix[i])) {
int num = ;
while (isdigit(postfix[i])) {
num = num * 10 + postfix[i] - '';
i++;
}
push(&s, num);
} else if (postfix[i] == '+') {
int b = pop(&s);
int a = pop(&s);
push(&s, a + b);
i++;
} else if (postfix[i] == '-') {
int b = pop(&s);
int a = pop(&s);
push(&s, a - b);
i++;
} else if (postfix[i] == '*') {
int b = pop(&s);
int a = pop(&s);
push(&s, a * b);
i++;
} else if (postfix[i] == '/') {
int b = pop(&s);
int a = pop(&s);
if (b == ) {
printf("Division by zero\n");
exit(1);
}
push(&s, a / b);
i++;
} else if (postfix[i] == ' ') {
i++;
} else {
printf("Invalid character: %c\n", postfix[i]);
exit(1);
}
}
if (s.top != ) {
printf("Invalid expression\n");
exit(1);
}
return pop(&s);
}
int main() {
char infix[MAX_SIZE];
char postfix[MAX_SIZE];
printf("Enter an infix expression: ");
fgets(infix, MAX_SIZE, stdin);
infix_to_postfix(infix, postfix);
printf("Postfix expression: %s\n", postfix);
printf("Value of postfix expression: %d\n", evaluate_postfix(postfix));
return ;
}
阅读全文