输入算术表达式转换后缀表达式

以下是一个用C语言编写的程序，能够实现中缀表达式与后缀表达式的转换，并对表达式进行求值： ```c #include <stdio.h> #include <stdlib.h> #include <ctype.h> #include <string.h> #define MAX 100 // 栈结构定义 typedef struct { char items[MAX]; 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 - 1; } // 入栈 void push(Stack *s, char c) { if (!isFull(s)) { s->items[++(s->top)] = c; } } // 出栈 char pop(Stack *s) { if (!isEmpty(s)) { return s->items[(s->top)--]; } return '\0'; } // 获取栈顶元素 char peek(Stack *s) { if (!isEmpty(s)) { return s->items[s->top]; } return '\0'; } // 判断字符是否为操作符 int isOperator(char c) { return c == '+' || c == '-' || c == '*' || c == '/'; } // 获取操作符优先级 int precedence(char c) { if (c == '*' || c == '/') { return 2; } else if (c == '+' || c == '-') { return 1; } return 0; } // 中缀表达式转换为后缀表达式 void infixToPostfix(char *infix, char *postfix) { Stack s; initStack(&s); int i = 0, j = 0; while (infix[i] != '\0') { char c = infix[i]; if (isspace(c)) { i++; continue; } if (isdigit(c) || isalpha(c)) { postfix[j++] = c; } else if (c == '(') { push(&s, c); } else if (c == ')') { while (!isEmpty(&s) && peek(&s) != '(') { postfix[j++] = pop(&s); } pop(&s); // 弹出 '(' } else if (isOperator(c)) { while (!isEmpty(&s) && precedence(peek(&s)) >= precedence(c)) { postfix[j++] = pop(&s); } push(&s, c); } i++; } while (!isEmpty(&s)) { postfix[j++] = pop(&s); } postfix[j] = '\0'; } // 后缀表达式求值 int evaluatePostfix(char *postfix) { Stack s; initStack(&s); int i = 0; while (postfix[i] != '\0') { char c = postfix[i]; if (isspace(c)) { i++; continue; } if (isdigit(c)) { push(&s, c - '0'); } else if (isOperator(c)) { int right = pop(&s) - '0'; int left = pop(&s) - '0'; int result; switch (c) { case '+': result = left + right; break; case '-': result = left - right; break; case '*': result = left * right; break; case '/': result = left / right; break; } push(&s, result + '0'); } i++; } return pop(&s) - '0'; } // 中缀表达式求值 int evaluateInfix(char *infix) { char postfix[MAX]; infixToPostfix(infix, postfix); return evaluatePostfix(postfix); } int main() { char infix[MAX], postfix[MAX]; printf("请输入中缀表达式: "); fgets(infix, MAX, stdin); infix[strcspn(infix, "\n")] = '\0'; // 去掉换行符 infixToPostfix(infix, postfix); printf("后缀表达式: %s\n", postfix); int result = evaluateInfix(infix); printf("表达式的值: %d\n", result); return 0; } ``` 这个程序实现了以下功能： 1. 将中缀表达式转换为后缀表达式。 2. 对后缀表达式进行求值。 3. 提供了直接对中缀表达式求值的功能。 4. 在主函数中测试了上述功能。 使用说明： 1. 输入中缀表达式时，可以用空格分隔各个元素，也可以不用。 2. 支持的运算符包括 +, -, *, /。 3. 支持使用括号 () 来改变运算顺序。 4. 支持整数运算。 这个程序可以作为算术表达式计算的基本框架。根据需要，你可以在此基础上进行扩展，比如增加更多的运算符、支持浮点数运算等。

要实现一个简单的计算器，我们首先需要解析输入的算术表达式，将其转换成后缀（逆波兰）表示法，再进行计算。这里我会给你提供一个基本的步骤和伪代码，具体到实际的C语言代码实现可能比较复杂，涉及到递归、语法分析以及数据结构如堆栈。 1. **解析输入表达式**: - 使用两个栈，一个用于存储操作数，另一个用于存储运算符。 - 遍历输入表达式，遇到数字就压入操作数栈，遇到运算符则检查优先级，如果当前运算符优先级高于或等于栈顶运算符，则将栈顶运算符弹出并压入运算符栈，直到找到一个优先级更低的运算符或遍历完输入表达式。 2. **转换为后缀表达式** (也称为逆波兰表达式): - 当遇到左括号时，直接压入栈。 - 遇到右括号时，重复弹出并运算操作数，直到遇到左括号为止，然后把左括号压回栈里。 - 遇到非括号字符，直接压入操作数栈。 3. **计算后缀表达式**: - 对于后缀表达式，从操作数栈开始取出元素，每次取出的操作数和运算符按照顺序进行相应的运算。 4. **最终结果**: - 计算完成后，操作数栈中的最后一个元素即为结果。 下面是简化的伪代码示例： ```pseudo function calculate(expression): stack = two stacks for operands and operators i = 0 while i < len(expression): if expression[i] is a digit or decimal point: push number onto operand stack until next non-digit character elif expression[i] is an operator: while top of operator stack has higher or equal priority: pop from both stacks, perform operation, and push result back on the operand stack push current operator to operator stack elif expression[i] is '(': push '(' onto operator stack elif expression[i] is ')': while top of operator stack isn't '(', pop and perform operations pop '(' from operator stack i += 1 while not empty in operator stack: pop from both stacks, perform operation, and push result back on the operand stack return top of operand stack as final result ```