C 中怎么将中缀表达式转换为后缀表达式（中缀表达式转后缀表达式c语言）

C 中怎么将中缀表达式转换为后缀表达式

C语言是一门非常重要的编程语言，它广泛应用于计算机科学领域。在C语言中，我们经常需要将中缀表达式转换为后缀表达式。本文将介绍如何使用C语言实现中缀表达式转后缀表达式。

中缀表达式是指运算符位于操作数之间的表达式，例如：1 + 2 * 3。而后缀表达式（也称为逆波兰表达式）则是指运算符位于操作数之后的表达式，例如：1 2 3 * +。

中缀表达式转后缀表达式的步骤如下：

1. 创建一个空栈和一个空字符串。

2. 从左到右遍历中缀表达式中的每个元素。

3. 如果当前元素是数字，则将其添加到输出字符串中。

4. 如果当前元素是左括号，则将其压入栈中。

5. 如果当前元素是右括号，则将栈中的元素弹出并添加到输出字符串中，直到遇到左括号为止。将左括号弹出但不添加到输出字符串中。

6. 如果当前元素是运算符，则将其与栈顶元素进行比较。如果栈顶元素优先级大于等于当前元素，则将栈顶元素弹出并添加到输出字符串中。重复此过程直到栈为空或栈顶元素优先级小于当前元素。将当前元素压入栈中。

7. 遍历完中缀表达式后，将栈中所有元素依次弹出并添加到输出字符串中。

8. 输出字符串即为后缀表达式。

以下是使用C语言实现中缀表达式转后缀表达式的代码：

```c

#include

#include

#include

#define MAX_SIZE 100

typedef struct {

char data[MAX_SIZE];

int top;

} Stack;

void push(Stack *s, char c) {

if (s->top == MAX_SIZE - 1) {

printf("Stack overflow\n");

exit(1);

}

s->data[++s->top] = c;

}

char pop(Stack *s) {

if (s->top == -1) {

printf("Stack underflow\n");

exit(1);

}

return s->data[s->top--];

}

int is_operator(char c) {

return (c == '+' || c == '-' || c == '*' || c == '/');

}

int precedence(char c) {

if (c == '+' || c == '-') {

return 1;

} else if (c == '*' || c == '/') {

return 2;

} else {

return 0;

}

}

void infix_to_postfix(char *infix, char *postfix) {

Stack s;

s.top = -1;

int i, j;

for (i = 0, j = 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 (s.data[s.top] != '(') {

postfix[j++] = pop(&s);

}

pop(&s);

} else if (is_operator(infix[i])) {

while (s.top != -1 && precedence(s.data[s.top]) >= precedence(infix[i])) {

postfix[j++] = pop(&s);

}

push(&s, infix[i]);

}

}

while (s.top != -1) {

postfix[j++] = pop(&s);

}

postfix[j] = '\0';

}

int main() {

char infix[MAX_SIZE], postfix[MAX_SIZE];

printf("Enter infix expression: ");

scanf("%s", infix);

infix_to_postfix(infix, postfix);

printf("Postfix expression: %s\n", postfix);

return 0;

}

```

以上代码定义了一个栈结构体，包含数据和栈顶指针。push函数将元素压入栈中，pop函数将元素弹出栈。is_operator函数判断字符是否为运算符，precedence函数返回运算符的优先级。infix_to_postfix函数实现了中缀表达式转后缀表达式的算法。最后，main函数读取用户输入的中缀表达式并调用infix_to_postfix函数将其转换为后缀表达式。

总之，C语言是一门非常强大的编程语言，可以实现各种各样的算法和应用程序。本文介绍了如何使用C语言实现中缀表达式转后缀表达式的算法，希望对读者有所帮助。