我想用c语言实现中缀式变成逆波兰式
时间: 2023-03-28 20:02:14 浏览: 64
好的,这个问题我可以回答。中缀式转换为逆波兰式需要用到栈的数据结构,具体实现可以参考以下步骤:
1. 创建一个栈,用于存储运算符。
2. 从左到右遍历中缀表达式的每个元素。
3. 如果当前元素是数字,则直接输出。
4. 如果当前元素是左括号,则将其压入栈中。
5. 如果当前元素是右括号,则将栈中的运算符依次弹出并输出,直到遇到左括号。
6. 如果当前元素是运算符,则将其与栈顶运算符比较,如果栈顶运算符优先级高于当前运算符,则将栈顶运算符弹出并输出,直到栈顶运算符优先级低于或等于当前运算符,然后将当前运算符压入栈中。
7. 遍历完中缀表达式后,将栈中剩余的运算符依次弹出并输出。
这样就可以将中缀表达式转换为逆波兰式了。
相关问题
用c语言写一个生成逆波兰式
以下是一个简单的生成逆波兰式的 C 语言程序:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_STACK_SIZE 100
char stack[MAX_STACK_SIZE][MAX_STACK_SIZE];
int top = -1;
void push(char* item)
{
if (top >= MAX_STACK_SIZE - 1) {
printf("Stack Overflow\n");
return;
}
top++;
strcpy(stack[top], item);
}
char* pop()
{
if (top == -1) {
printf("Stack Underflow\n");
return NULL;
}
char* item = stack[top];
top--;
return item;
}
int is_operator(char* symbol)
{
if (strcmp(symbol, "+") == 0 || strcmp(symbol, "-") == 0 || strcmp(symbol, "*") == 0 || strcmp(symbol, "/") == 0) {
return 1;
}
return 0;
}
int precedence(char* symbol)
{
if (strcmp(symbol, "*") == 0 || strcmp(symbol, "/") == 0) {
return 2;
}
else if (strcmp(symbol, "+") == 0 || strcmp(symbol, "-") == 0) {
return 1;
}
return 0;
}
void infix_to_postfix(char* infix_expression, char* postfix_expression)
{
int i = 0, j = 0;
char* symbol;
while (infix_expression[i] != '\0') {
symbol = (char*)malloc(MAX_STACK_SIZE * sizeof(char));
while (infix_expression[i] == ' ' || infix_expression[i] == '\t') {
i++;
}
symbol[0] = infix_expression[i];
if (isdigit(infix_expression[i])) {
j = i + 1;
while (isdigit(infix_expression[j])) {
j++;
}
strncpy(&symbol[1], &infix_expression[i + 1], j - i - 1);
symbol[j - i] = '\0';
strcat(postfix_expression, symbol);
strcat(postfix_expression, " ");
i = j;
}
else if (is_operator(symbol)) {
while (top != -1 && precedence(stack[top]) >= precedence(symbol)) {
strcat(postfix_expression, pop());
strcat(postfix_expression, " ");
}
push(symbol);
i++;
}
else if (symbol[0] == '(') {
push(symbol);
i++;
}
else if (symbol[0] == ')') {
while (top != -1 && stack[top][0] != '(') {
strcat(postfix_expression, pop());
strcat(postfix_expression, " ");
}
pop();
i++;
}
free(symbol);
}
while (top != -1) {
strcat(postfix_expression, pop());
strcat(postfix_expression, " ");
}
}
int main()
{
char infix_expression[MAX_STACK_SIZE], postfix_expression[MAX_STACK_SIZE];
printf("Enter Infix Expression : ");
gets(infix_expression);
infix_to_postfix(infix_expression, postfix_expression);
printf("Postfix Expression : %s", postfix_expression);
return 0;
}
```
该程序使用栈数据结构将中缀表达式转换为逆波兰式。输入中缀表达式后,程序将空格分隔的逆波兰式输出到屏幕上。
编译原理用c语言实现逆波兰式的生成和计算
下面是使用 C 语言实现逆波兰式的生成和计算的代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#define MAX_STACK_SIZE 100
#define MAX_EXPR_SIZE 100
typedef struct {
int top;
char data[MAX_STACK_SIZE][MAX_EXPR_SIZE];
} 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 == MAX_STACK_SIZE - 1;
}
void push(Stack *s, char *x) {
if (is_full(s)) {
printf("Stack overflow.\n");
exit(1);
}
strcpy(s->data[++s->top], x);
}
char *pop(Stack *s) {
if (is_empty(s)) {
printf("Stack underflow.\n");
exit(1);
}
return s->data[s->top--];
}
int is_operator(char *op) {
return (strcmp(op, "+") == 0 ||
strcmp(op, "-") == 0 ||
strcmp(op, "*") == 0 ||
strcmp(op, "/") == 0);
}
int get_precedence(char *op) {
if (strcmp(op, "+") == 0 || strcmp(op, "-") == 0) {
return 1;
} else if (strcmp(op, "*") == 0 || strcmp(op, "/") == 0) {
return 2;
} else {
return 0;
}
}
void infix_to_postfix(char *infix, char *postfix) {
Stack op_stack;
init_stack(&op_stack);
char *p = infix;
char *q = postfix;
while (*p) {
if (isdigit(*p)) {
while (isdigit(*p)) {
*q++ = *p++;
}
*q++ = ' ';
} else if (is_operator(p)) {
while (!is_empty(&op_stack) &&
get_precedence(p) <= get_precedence(op_stack.data[op_stack.top])) {
strcat(q, pop(&op_stack));
strcat(q, " ");
}
push(&op_stack, p);
p++;
} else if (*p == '(') {
push(&op_stack, p);
p++;
} else if (*p == ')') {
while (op_stack.data[op_stack.top][0] != '(') {
strcat(q, pop(&op_stack));
strcat(q, " ");
}
pop(&op_stack);
p++;
} else {
p++;
}
}
while (!is_empty(&op_stack)) {
strcat(q, pop(&op_stack));
strcat(q, " ");
}
}
int evaluate_postfix(char *postfix) {
Stack op_stack;
init_stack(&op_stack);
char *p = postfix;
while (*p) {
if (isdigit(*p)) {
int num = 0;
while (isdigit(*p)) {
num = num * 10 + (*p - '0');
p++;
}
push(&op_stack, num);
} else if (is_operator(p)) {
int a = atoi(pop(&op_stack));
int b = atoi(pop(&op_stack));
int result;
if (strcmp(p, "+") == 0) {
result = b + a;
} else if (strcmp(p, "-") == 0) {
result = b - a;
} else if (strcmp(p, "*") == 0) {
result = b * a;
} else if (strcmp(p, "/") == 0) {
result = b / a;
}
char temp[MAX_EXPR_SIZE];
sprintf(temp, "%d", result);
push(&op_stack, temp);
p++;
} else {
p++;
}
}
return atoi(pop(&op_stack));
}
int main() {
char infix_expr[MAX_EXPR_SIZE];
printf("Enter an infix expression: ");
scanf("%[^\n]%*c", infix_expr);
char postfix_expr[MAX_EXPR_SIZE];
infix_to_postfix(infix_expr, postfix_expr);
printf("Postfix expression: %s\n", postfix_expr);
int result = evaluate_postfix(postfix_expr);
printf("Result: %d\n", result);
return 0;
}
```
这段代码中,我们首先实现了将中缀表达式转换为后缀表达式的函数 `infix_to_postfix`,然后实现了利用后缀表达式进行计算的函数 `evaluate_postfix`。在中缀转后缀的过程中,我们使用了栈来存储运算符,并在遍历完整个表达式后将栈中剩余的运算符弹出并添加到后缀表达式中。在计算后缀表达式的过程中,我们同样使用了栈来存储数字,并在遍历完整个表达式后将栈中剩余的数字弹出并进行运算。