c++实现任意算术表达式转化为后缀表达式代码实现
时间: 2023-06-11 08:10:15 浏览: 69
下面是一个C语言实现任意算术表达式转化为后缀表达式的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#define STACK_INIT_SIZE 20
#define STACK_INCREMENT 10
#define MAX_EXPRESSION_LEN 100
typedef struct {
char *base;
char *top;
int stack_size;
} Stack;
void InitStack(Stack *s) {
s->base = (char *)malloc(STACK_INIT_SIZE * sizeof(char));
if (!s->base) {
exit(1);
}
s->top = s->base;
s->stack_size = STACK_INIT_SIZE;
}
void Push(Stack *s, char e) {
if (s->top - s->base >= s->stack_size) {
s->base = (char *)realloc(s->base, (s->stack_size + STACK_INCREMENT) * sizeof(char));
if (!s->base) {
exit(1);
}
s->top = s->base + s->stack_size;
s->stack_size += STACK_INCREMENT;
}
*(s->top) = e;
s->top++;
}
char Pop(Stack *s) {
if (s->top == s->base) {
exit(1);
}
char e = *(--s->top);
return e;
}
char GetTop(Stack *s) {
if (s->top == s->base) {
exit(1);
}
return *(s->top - 1);
}
int IsEmpty(Stack *s) {
if (s->top == s->base) {
return 1;
} else {
return 0;
}
}
int GetPriority(char op) {
switch (op) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '(':
return 0;
default:
return -1;
}
}
void InfixToPostfix(char *infix, char *postfix) {
Stack s;
InitStack(&s);
char c;
char *p = infix;
char *q = postfix;
while (*p != '\0') {
if (isdigit(*p) || isalpha(*p)) {
*q = *p;
q++;
} else if (*p == '(') {
Push(&s, *p);
} else if (*p == ')') {
while (GetTop(&s) != '(') {
*q = Pop(&s);
q++;
}
Pop(&s);
} else if (*p == '+' || *p == '-' || *p == '*' || *p == '/') {
while (!IsEmpty(&s) && GetPriority(GetTop(&s)) >= GetPriority(*p)) {
*q = Pop(&s);
q++;
}
Push(&s, *p);
} else {
printf("Invalid input.\n");
exit(1);
}
p++;
}
while (!IsEmpty(&s)) {
*q = Pop(&s);
q++;
}
*q = '\0';
}
int main() {
char infix[MAX_EXPRESSION_LEN];
char postfix[MAX_EXPRESSION_LEN];
printf("Enter an infix expression: ");
fgets(infix, MAX_EXPRESSION_LEN, stdin);
infix[strlen(infix) - 1] = '\0';
InfixToPostfix(infix, postfix);
printf("The postfix expression is: %s\n", postfix);
return 0;
}
```
该程序使用栈来实现算术表达式的转换。具体实现过程如下:
1. 初始化一个栈;
2. 从左到右扫描中缀表达式;
3. 如果遇到数字或者字母,就将其添加到后缀表达式中;
4. 如果遇到左括号,就将其压入栈中;
5. 如果遇到右括号,则将栈中的元素弹出,直到遇到左括号为止。左右括号不加入后缀表达式中;
6. 如果遇到运算符,就比较它和栈顶运算符的优先级,如果栈顶运算符的优先级大于或等于当前运算符的优先级,则弹出栈顶运算符,直到栈为空或者栈顶运算符的优先级小于当前运算符的优先级。将当前运算符压入栈中;
7. 当扫描完整个中缀表达式后,如果栈中还有元素,就将其弹出并添加到后缀表达式中;
8. 输出后缀表达式。
其中,优先级使用 GetPriority 函数实现。该函数返回运算符的优先级,用于比较栈顶运算符和当前运算符的优先级。如果当前字符既不是数字和字母,也不是括号,就说明输入的表达式有误,程序将退出。