写一个c++的中缀表达式转换成后缀表达式的程序
时间: 2023-05-25 15:06:41 浏览: 112
C++实现中缀表达式转后缀表达式
5星 · 资源好评率100%
在这里给出一个C语言的中缀表达式转换成后缀表达式的程序:
```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define STACK_SIZE 100 // 栈的最大容量
typedef struct stack {
char data[STACK_SIZE]; // 栈中存储的数据
int top; // 栈顶指针
} stack;
/* 初始化栈 */
void init_stack(stack *s) {
s->top = -1;
}
/* 判断栈空 */
int is_empty(stack *s) {
return s->top == -1;
}
/* 判断栈满 */
int is_full(stack *s) {
return s->top == STACK_SIZE - 1;
}
/* 入栈 */
void push(stack *s, char c) {
if (is_full(s)) {
fprintf(stderr, "Stack overflow!\n");
exit(1);
}
s->data[++(s->top)] = c;
}
/* 出栈 */
char pop(stack *s) {
if (is_empty(s)) {
fprintf(stderr, "Stack underflow!\n");
exit(1);
}
return s->data[(s->top)--];
}
/* 获取栈顶元素 */
char get_top(stack *s) {
if (is_empty(s)) {
fprintf(stderr, "Stack underflow!\n");
exit(1);
}
return s->data[s->top];
}
/* 判断运算符优先级 */
int priority(char op) {
if (op == '+' || op == '-') {
return 1;
} else if (op == '*' || op == '/') {
return 2;
} else {
return 0;
}
}
/* 中缀表达式转换成后缀表达式 */
void infix_to_postfix(char *infix, char *postfix) {
stack s; // 运算符栈
char c, op;
int i, j = 0;
init_stack(&s); // 初始化栈
for (i = 0; i < strlen(infix); i++) {
c = infix[i];
if (c >= '0' && c <= '9') { // 数字直接输出
postfix[j++] = c;
} else if (c == '(') { // 左括号入栈
push(&s, c);
} else if (c == ')') { // 右括号弹出运算符直到遇到左括号
while (get_top(&s) != '(') {
postfix[j++] = pop(&s);
}
pop(&s);
} else if (c == '+' || c == '-' || c == '*' || c == '/') { // 运算符处理
if (is_empty(&s) || get_top(&s) == '(' || priority(c) > priority(get_top(&s))) {
push(&s, c);
} else {
do {
op = pop(&s);
postfix[j++] = op;
} while (!is_empty(&s) && op != '(' && priority(c) <= priority(get_top(&s)));
push(&s, c);
}
} else { // 非法字符
fprintf(stderr, "Invalid character!\n");
exit(1);
}
}
while (!is_empty(&s)) { // 依次弹出栈中剩余的运算符
postfix[j++] = pop(&s);
}
postfix[j] = '\0'; // 转换完毕,添加字符串结束符
}
/* 主函数 */
int main() {
char infix[STACK_SIZE]; // 中缀表达式
char postfix[STACK_SIZE]; // 后缀表达式
printf("请输入中缀表达式:");
scanf("%s", infix); // 读取中缀表达式
infix_to_postfix(infix, postfix); // 转换为后缀表达式
printf("后缀表达式为:%s\n", postfix); // 输出后缀表达式
return 0;
}
```
程序流程如下:
1. 定义栈结构体和栈的操作函数。
2. 定义运算符的优先级函数。
3. 定义中缀表达式转换成后缀表达式的函数。
4. 在主函数中读入中缀表达式并调用函数进行转换,输出后缀表达式。
5. 程序结束。
该程序的主要思想是通过一个运算符栈来实现中缀表达式转换为后缀表达式。遍历中缀表达式,当遇到数字时直接输出到后缀表达式中,遇到左括号时入栈,遇到右括号时弹出栈中的运算符并输出到后缀表达式中,直到遇到左括号为止。当遇到运算符时,将栈中的运算符弹出并输出到后缀表达式中,直到栈为空或栈顶为左括号或新的运算符优先级高于栈顶运算符为止,最后将新的运算符入栈。当遍历完中缀表达式后,将剩余的运算符依次弹出并输出到后缀表达式中即可。
阅读全文