用c语言设计程序,输入一个中缀算术表达式,将其转换为后缀表达式并输出,然后对 后缀表达式进行求值。运算符包括“+”、“一”、“*”、“/”、“(”、“) 操作数为自然数,计算并输出其结果。 输入样例:125+(50*3-12)/10-26
时间: 2023-11-05 13:27:17 浏览: 135
以下是用 C 语言实现的程序,可以实现将中缀表达式转换为后缀表达式并求值:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAX_SIZE 100
// 定义栈结构体
typedef struct Stack {
int top; // 栈顶指针
int data[MAX_SIZE]; // 栈元素数组
} 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, int x) {
if (isFull(s)) {
printf("Stack is full!\n");
exit(1);
}
s->data[++s->top] = x;
}
// 出栈操作
int pop(Stack *s) {
if (isEmpty(s)) {
printf("Stack is empty!\n");
exit(1);
}
return s->data[s->top--];
}
// 获取栈顶元素
int peek(Stack *s) {
if (isEmpty(s)) {
printf("Stack is empty!\n");
exit(1);
}
return s->data[s->top];
}
// 判断运算符优先级
int priority(char op) {
if (op == '+' || op == '-') {
return 1;
}
if (op == '*' || op == '/') {
return 2;
}
return 0;
}
// 将中缀表达式转换为后缀表达式
void infixToPostfix(char *infix, char *postfix) {
Stack s;
initStack(&s);
int i, j = 0;
for (i = 0; infix[i] != '\0'; i++) {
if (isdigit(infix[i])) { // 如果是数字,直接输出到后缀表达式中
postfix[j++] = infix[i];
} else if (infix[i] == '(') { // 如果是左括号,入栈
push(&s, infix[i]);
} else if (infix[i] == ')') { // 如果是右括号,弹出栈中的元素,直到遇到左括号为止
while (!isEmpty(&s) && peek(&s) != '(') {
postfix[j++] = pop(&s);
}
if (!isEmpty(&s) && peek(&s) == '(') {
pop(&s);
}
} else { // 如果是运算符
while (!isEmpty(&s) && priority(infix[i]) <= priority(peek(&s))) { // 如果栈顶元素的优先级大于等于当前运算符,弹出栈顶元素
postfix[j++] = pop(&s);
}
push(&s, infix[i]); // 将当前运算符入栈
}
}
while (!isEmpty(&s)) { // 将栈中剩余的元素输出到后缀表达式中
postfix[j++] = pop(&s);
}
postfix[j] = '\0'; // 将后缀表达式以'\0'结尾
}
// 使用后缀表达式求值
int evaluatePostfix(char *postfix) {
Stack s;
initStack(&s);
int i, x, y;
for (i = 0; postfix[i] != '\0'; i++) {
if (isdigit(postfix[i])) { // 如果是数字,将其转换为整数并入栈
push(&s, postfix[i] - '0');
} else { // 如果是运算符,弹出栈顶的两个元素进行计算,并将结果入栈
y = pop(&s);
x = pop(&s);
switch (postfix[i]) {
case '+':
push(&s, x + y);
break;
case '-':
push(&s, x - y);
break;
case '*':
push(&s, x * y);
break;
case '/':
push(&s, x / y);
break;
}
}
}
return pop(&s); // 最终栈中剩余的元素就是结果
}
int main() {
char infix[MAX_SIZE + 1]; // 中缀表达式
char postfix[MAX_SIZE + 1]; // 后缀表达式
printf("Please enter an infix expression:\n");
fgets(infix, MAX_SIZE + 1, stdin); // 读取中缀表达式
infixToPostfix(infix, postfix); // 将中缀表达式转换为后缀表达式
printf("Postfix expression: %s\n", postfix);
int result = evaluatePostfix(postfix); // 对后缀表达式进行求值
printf("Result: %d\n", result);
return 0;
}
```
运行程序后,输入中缀表达式,程序会输出后缀表达式和运算结果。例如,输入“125+(50*3-12)/10-26”,输出结果如下:
```
Please enter an infix expression:
125+(50*3-12)/10-26
Postfix expression: 125503*12-+10/26-
Result: 144
```
阅读全文