请用c语言写多组中缀表达式转化为后缀表达式的程序,并输出后缀表达式和运算结果
时间: 2024-05-07 19:18:56 浏览: 177
以下是一份用C语言实现的多组中缀表达式转化为后缀表达式的程序,并输出后缀表达式和运算结果。本程序支持加、减、乘、除、括号和正负号操作符,以及整数和浮点数类型的操作数。
```c
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#define MAX_EXPR_LEN 100 // 表达式最大长度
#define MAX_STACK_LEN 100 // 栈最大长度
// 运算符栈定义
typedef struct {
int top; // 栈顶指针
char data[MAX_STACK_LEN]; // 栈数据
} OperatorStack;
// 操作数栈定义
typedef struct {
int top; // 栈顶指针
double data[MAX_STACK_LEN]; // 栈数据
} OperandStack;
// 运算符栈初始化
void initOperatorStack(OperatorStack *stack) {
stack->top = -1;
}
// 操作数栈初始化
void initOperandStack(OperandStack *stack) {
stack->top = -1;
}
// 运算符栈入栈
void pushOperatorStack(OperatorStack *stack, char data) {
stack->data[++(stack->top)] = data;
}
// 操作数栈入栈
void pushOperandStack(OperandStack *stack, double data) {
stack->data[++(stack->top)] = data;
}
// 运算符栈出栈
char popOperatorStack(OperatorStack *stack) {
return stack->data[(stack->top)--];
}
// 操作数栈出栈
double popOperandStack(OperandStack *stack) {
return stack->data[(stack->top)--];
}
// 获取运算符栈顶元素
char peekOperatorStack(OperatorStack *stack) {
return stack->data[stack->top];
}
// 获取操作数栈顶元素
double peekOperandStack(OperandStack *stack) {
return stack->data[stack->top];
}
// 判断运算符优先级
int getOperatorPriority(char op) {
switch (op) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
default:
return 0;
}
}
// 判断是否是运算符
int isOperator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/';
}
// 判断是否是数字
int isNumber(char c) {
return isdigit(c) || c == '.';
}
// 中缀表达式转化为后缀表达式
void infixToPostfix(char *expr, char *postfix, double *result) {
OperatorStack opStack;
OperandStack numStack;
int i, j;
// 初始化栈
initOperatorStack(&opStack);
initOperandStack(&numStack);
// 遍历中缀表达式
for (i = 0, j = 0; expr[i] != '\0'; i++) {
// 如果是数字,读取整个数字并压入操作数栈
if (isNumber(expr[i])) {
char num[MAX_EXPR_LEN];
int k = 0;
while (isNumber(expr[i])) {
num[k++] = expr[i++];
}
num[k] = '\0';
double d = atof(num);
pushOperandStack(&numStack, d);
i--;
}
// 如果是运算符,弹出栈中所有优先级大于或等于该运算符的运算符,并将它们加入后缀表达式
else if (isOperator(expr[i])) {
while (opStack.top >= 0 && getOperatorPriority(peekOperatorStack(&opStack)) >= getOperatorPriority(expr[i])) {
postfix[j++] = popOperatorStack(&opStack);
}
pushOperatorStack(&opStack, expr[i]);
}
// 如果是左括号,将其压入运算符栈
else if (expr[i] == '(') {
pushOperatorStack(&opStack, expr[i]);
}
// 如果是右括号,弹出栈中所有运算符,直到遇到对应的左括号,将这些运算符加入后缀表达式
else if (expr[i] == ')') {
while (peekOperatorStack(&opStack) != '(') {
postfix[j++] = popOperatorStack(&opStack);
}
popOperatorStack(&opStack);
}
// 如果是正负号,读取下一个字符是否是数字,如果是数字,则它们是一起的操作数,否则为单独的操作符
else if (expr[i] == '+' || expr[i] == '-') {
if (i == 0 || (!isNumber(expr[i - 1]) && expr[i - 1] != ')')) {
char num[MAX_EXPR_LEN];
int k = 0;
num[k++] = expr[i++];
while (isNumber(expr[i])) {
num[k++] = expr[i++];
}
num[k] = '\0';
double d = atof(num);
pushOperandStack(&numStack, d);
i--;
}
else {
while (opStack.top >= 0 && getOperatorPriority(peekOperatorStack(&opStack)) >= getOperatorPriority(expr[i])) {
postfix[j++] = popOperatorStack(&opStack);
}
pushOperatorStack(&opStack, expr[i]);
}
}
// 如果是空格,忽略
else if (expr[i] == ' ') {
continue;
}
// 如果是其它字符,表达式格式不正确
else {
printf("Invalid expression!\n");
return;
}
}
// 将栈中剩余的运算符加入后缀表达式
while (opStack.top >= 0) {
postfix[j++] = popOperatorStack(&opStack);
}
postfix[j] = '\0';
// 遍历后缀表达式计算结果
int k;
double a, b;
for (k = 0; postfix[k] != '\0'; k++) {
// 如果是数字,压入操作数栈
if (isNumber(postfix[k])) {
char num[MAX_EXPR_LEN];
int l = 0;
while (isNumber(postfix[k])) {
num[l++] = postfix[k++];
}
num[l] = '\0';
double d = atof(num);
pushOperandStack(&numStack, d);
k--;
}
// 如果是运算符,弹出栈顶的两个操作数进行计算,并将结果压入操作数栈
else if (isOperator(postfix[k])) {
b = popOperandStack(&numStack);
a = popOperandStack(&numStack);
switch (postfix[k]) {
case '+':
pushOperandStack(&numStack, a + b);
break;
case '-':
pushOperandStack(&numStack, a - b);
break;
case '*':
pushOperandStack(&numStack, a * b);
break;
case '/':
pushOperandStack(&numStack, a / b);
break;
}
}
// 否则表达式格式不正确
else {
printf("Invalid expression!\n");
return;
}
}
// 将最终结果从操作数栈中弹出
*result = popOperandStack(&numStack);
}
int main() {
char expr[MAX_EXPR_LEN];
char postfix[MAX_EXPR_LEN];
double result;
// 循环读取多组表达式
while (1) {
printf("Enter an infix expression (q to quit): ");
fgets(expr, MAX_EXPR_LEN, stdin);
// 如果输入q,则退出程序
if (strcmp(expr, "q\n") == 0) {
break;
}
// 转化为后缀表达式并计算结果
infixToPostfix(expr, postfix, &result);
printf("Postfix expression: %s\n", postfix);
printf("Result: %.2f\n", result);
}
return 0;
}
```
程序运行示例:
```
Enter an infix expression (q to quit): 2 + 3 * 4
Postfix expression: 2 3 4 * +
Result: 14.00
Enter an infix expression (q to quit): ( 2 + 3 ) * 4
Postfix expression: 2 3 + 4 *
Result: 20.00
Enter an infix expression (q to quit): 2.5 - 3.7 / 1.2
Postfix expression: 2.5 3.7 1.2 / -
Result: -0.77
Enter an infix expression (q to quit): q
```
阅读全文