c语言将表达式转化为波兰式和逆波兰式

C语言中将表达式转化为波兰式和逆波兰式的方法是使用栈来实现。波兰式（前缀式）指的是运算符号位于其对应的操作数之前，而逆波兰式（后缀式）指的是运算符号位于其对应的操作数之后。

将中缀表达式转换为前缀或后缀表达式可以通过以下步骤进行：

1. 创建一个符号栈（Stack）和一个结果队列（Queue）。

2. 从左到右扫描中缀表达式，若遇到操作数，将其加入到结果队列中。

3. 若遇到运算符，比较其与栈顶运算符的优先级，若优先级低于栈顶元素，则将栈顶元素弹出并加入到结果队列中，直接层层递进，直到遇到比该元素优先级较低的元素为止。

4. 若遇到左括号“（”，则将其入栈。

5. 若遇到右括号“）”，则依次弹出栈顶元素，加入到结果队列中，直到左括号“（”被弹出。注意：左括号“（”不加入到结果队列中。

6. 最后，如果符号栈中仍有元素，则依次弹出加入到结果队列中。

7. 若要将中缀表达式转换为逆波兰式，则将符号栈改为栈，并将操作数加入到栈中。

8. 遇到运算符时，弹出栈顶的两个操作数进行计算，并将结果压入栈中。

9. 最后栈中仅剩一个元素，即为逆波兰式。

注意事项：

在将中缀表达式转换为前缀表达式时，我们需要先将中缀表达式翻转，再按照转换成后缀表达式的方法进行。

在计算逆波兰式时，需要注意操作数的顺序，因为后缀式在操作数的顺序上没有明确的要求。

相关问题

设计一个算法，将一般算术表达式转化为逆波兰表达式，并求逆波兰表达 式的值C语言

我可以回答这个问题。将一般算术表达式转化为逆波兰表达式的算法可以使用栈来实现。具体步骤如下：

1. 创建一个栈，用于存储运算符和操作数。
2. 从左到右扫描表达式的每个元素，如果是操作数，则将其压入栈中。
3. 如果是运算符，则弹出栈顶的两个操作数，进行运算，并将结果压入栈中。
4. 重复步骤2和3，直到扫描完整个表达式。
5. 最后栈中只剩下一个元素，即为逆波兰表达式的值。

以下是一个示例代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define MAX_SIZE 100

typedef struct {
int top;
int data[MAX_SIZE];
} Stack;

void init(Stack *s) {
s->top = -1;
}

void push(Stack *s, int x) {
if (s->top == MAX_SIZE - 1) {
printf("Stack overflow\n");
exit(1);
}
s->data[++s->top] = x;
}

int 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) {
switch (c) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
default:
return ;
}
}

void infix_to_postfix(char *infix, char *postfix) {
Stack s;
init(&s);
int i = , j = ;
while (infix[i] != '\') {
if (isdigit(infix[i])) {
postfix[j++] = infix[i++];
while (isdigit(infix[i])) {
postfix[j++] = infix[i++];
}
postfix[j++] = ' ';
} else if (is_operator(infix[i])) {
while (s.top != -1 && is_operator(s.data[s.top]) && precedence(s.data[s.top]) >= precedence(infix[i])) {
postfix[j++] = pop(&s);
postfix[j++] = ' ';
}
push(&s, infix[i++]);
} else if (infix[i] == '(') {
push(&s, infix[i++]);
} else if (infix[i] == ')') {
while (s.top != -1 && s.data[s.top] != '(') {
postfix[j++] = pop(&s);
postfix[j++] = ' ';
}
if (s.top == -1) {
printf("Mismatched parentheses\n");
exit(1);
}
pop(&s);
i++;
} else if (isspace(infix[i])) {
i++;
} else {
printf("Invalid character: %c\n", infix[i]);
exit(1);
}
}
while (s.top != -1) {
if (s.data[s.top] == '(') {
printf("Mismatched parentheses\n");
exit(1);
}
postfix[j++] = pop(&s);
postfix[j++] = ' ';
}
postfix[j] = '\';
}

int evaluate_postfix(char *postfix) {
Stack s;
init(&s);
int i = ;
while (postfix[i] != '\') {
if (isdigit(postfix[i])) {
int num = ;
while (isdigit(postfix[i])) {
num = num * 10 + postfix[i] - '';
i++;
}
push(&s, num);
} else if (postfix[i] == '+') {
int b = pop(&s);
int a = pop(&s);
push(&s, a + b);
i++;
} else if (postfix[i] == '-') {
int b = pop(&s);
int a = pop(&s);
push(&s, a - b);
i++;
} else if (postfix[i] == '*') {
int b = pop(&s);
int a = pop(&s);
push(&s, a * b);
i++;
} else if (postfix[i] == '/') {
int b = pop(&s);
int a = pop(&s);
if (b == ) {
printf("Division by zero\n");
exit(1);
}
push(&s, a / b);
i++;
} else if (postfix[i] == ' ') {
i++;
} else {
printf("Invalid character: %c\n", postfix[i]);
exit(1);
}
}
if (s.top != ) {
printf("Invalid expression\n");
exit(1);
}
return pop(&s);
}

int main() {
char infix[MAX_SIZE];
char postfix[MAX_SIZE];
printf("Enter an infix expression: ");
fgets(infix, MAX_SIZE, stdin);
infix_to_postfix(infix, postfix);
printf("Postfix expression: %s\n", postfix);
printf("Value of postfix expression: %d\n", evaluate_postfix(postfix));
return ;
}

（1）将只包含+、—、*、/和（）的算术表达式转化为逆波兰式（后缀式）；的C语言代码

以下是一个将算术表达式转化为逆波兰式的C语言实现，使用了栈来实现：

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

#define MAX_EXPR_LEN 100
#define MAX_STACK_SIZE 100

char expr[MAX_EXPR_LEN];
int stack[MAX_STACK_SIZE], top = -1;

int precedence(char op) {
    switch (op) {
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        default:
            return 0;
    }
}

void push(int val) {
    if (top == MAX_STACK_SIZE - 1) {
        printf("Error: Stack overflow\n");
        exit(EXIT_FAILURE);
    }
    stack[++top] = val;
}

int pop() {
    if (top == -1) {
        printf("Error: Stack underflow\n");
        exit(EXIT_FAILURE);
    }
    return stack[top--];
}

int main() {
    printf("Enter an arithmetic expression: ");
    fgets(expr, MAX_EXPR_LEN, stdin);

    int i = 0, num;
    while (expr[i] != '\0') {
        if (isdigit(expr[i])) {
            num = 0;
            while (isdigit(expr[i])) {
                num = num * 10 + (expr[i] - '0');
                i++;
            }
            printf("%d ", num);
        } else if (isspace(expr[i])) {
            i++;
        } else {
            while (top >= 0 && precedence(stack[top]) >= precedence(expr[i])) {
                printf("%c ", pop());
            }
            push(expr[i]);
            i++;
        }
    }

    while (top >= 0) {
        printf("%c ", pop());
    }

    return 0;
}

该程序首先读取用户输入的算术表达式，然后按顺序扫描表达式中的每个字符。如果字符是数字，则将其转换为数字并直接输出；如果字符是操作符，则将其与栈顶的操作符比较，如果栈顶的操作符优先级大于等于当前操作符，则将栈顶的操作符弹出并输出，然后将当前操作符压入栈中。最后，将栈中剩余的操作符全部弹出并输出。输出的结果就是逆波兰式。