C语言实现逆波兰式实例
逆波兰式是一种数学表达式表示法，也称为后缀表达式。与常见的表达式表示法不同，逆波兰式将操作数放在操作符之前，能够方便地使用栈等数据结构进行表达式的求解。在C语言中实现逆波兰式求值可以采用栈的数据结构进行实现。本文将介绍基于栈的C语言实现逆波兰式的完整攻略。
逆波兰式的基本原理
逆波兰式可以通过以下步骤进行转换：
- 从左到右扫描中缀表达式。
- 遇到操作符时，将其压入栈中。
- 遇到操作数时，将其输出。
- 遇到右括号时，将操作符弹出并输出，直到遇到左括号。
- 如果遇到其他操作符，判断其与栈顶操作符的优先级关系，如果栈顶操作符的优先级大于该操作符，则将栈顶操作符弹出并输出，再将该操作符压入栈中。
- 重复步骤2-5，直到将中缀表达式转换为后缀表达式。
C语言实现逆波兰式的基本步骤
- 定义一个栈结构体，包含栈顶指针以及栈的大小等信息。
- 定义一个函数，用于将中缀表达式转换为后缀表达式，其中使用栈来维护操作符。
- 定义一个函数，用于计算后缀表达式的值，其中使用栈来维护操作数。
示例说明1：将中缀表达式转换为后缀表达式
以下为一个简单的例子：
#include <stdio.h>
#define MAXSIZE 100
typedef enum {
OP_PLUS = '+',
OP_MINUS = '-',
OP_MULTIPLY = '*',
OP_DIVIDE = '/',
OP_LEFT_PARENTHESES = '(',
OP_RIGHT_PARENTHESES = ')',
OP_END = '\0'
} operator;
typedef struct {
operator* top;
operator* stack;
int size;
} operator_stack;
void operator_push(operator_stack* stack, operator op) {
if (stack->top - stack->stack >= stack->size) {
printf("stack is full\n");
return;
}
*(++stack->top) = op;
}
operator operator_pop(operator_stack* stack) {
if (stack->top == stack->stack) {
printf("stack is empty\n");
return OP_END;
}
return *(stack->top--);
}
operator operator_top(operator_stack* stack) {
if (stack->top == stack->stack) {
printf("stack is empty\n");
return OP_END;
}
return *(stack->top);
}
operator_stack* operator_stack_create(int size) {
operator_stack* stack = (operator_stack*) malloc(sizeof(operator_stack));
stack->top = stack->stack - 1;
stack->stack = (operator*) malloc(sizeof(operator) * size);
stack->size = size;
return stack;
}
void operator_stack_destroy(operator_stack* stack) {
free(stack->stack);
stack->stack = NULL;
stack->top = NULL;
stack->size = 0;
free(stack);
}
int is_number(char ch) {
return ch >= '0' && ch <= '9';
}
int is_operator(char ch) {
return ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '(' || ch == ')';
}
int is_higher_priority(operator op1, operator op2) {
switch (op1) {
case OP_DIVIDE:
case OP_MULTIPLY:
return op2 == OP_PLUS || op2 == OP_MINUS;
case OP_PLUS:
case OP_MINUS:
return op2 == OP_LEFT_PARENTHESES;
case OP_LEFT_PARENTHESES:
default:
return 0;
}
}
void infix_to_postfix(char* infix, char* postfix, int size) {
operator_stack* stack = operator_stack_create(size);
operator_push(stack, OP_LEFT_PARENTHESES);
int i = 0;
int j = 0;
while (infix[i] != '\0') {
char ch = infix[i++];
if (is_number(ch)) {
postfix[j++] = ch;
} else if (is_operator(ch)) {
if (ch == OP_LEFT_PARENTHESES) {
operator_push(stack, ch);
} else if (ch == OP_RIGHT_PARENTHESES) {
operator top = operator_pop(stack);
while (top != OP_LEFT_PARENTHESES) {
postfix[j++] = top;
top = operator_pop(stack);
}
} else {
operator top = operator_top(stack);
while (is_higher_priority(top, ch)) {
postfix[j++] = operator_pop(stack);
top = operator_top(stack);
}
operator_push(stack, ch);
}
} else {
printf("invalid character: %c\n", ch);
}
}
while (stack->top != stack->stack) {
postfix[j++] = operator_pop(stack);
}
postfix[j] = '\0';
operator_stack_destroy(stack);
}
int main() {
char infix[MAXSIZE] = "3+4*5/(6+7)-8";
char postfix[MAXSIZE];
infix_to_postfix(infix, postfix, MAXSIZE);
printf("infix: %s\npostfix: %s\n", infix, postfix);
return 0;
}
在上面的示例代码中，我们定义了一个操作符栈来维护中缀表达式转换为后缀表达式的过程。其中operator_push、operator_pop和operator_top函数是操作栈的基本函数。is_higher_priority函数用来判断两个操作符的优先级。infix_to_postfix函数用来将中缀表达式转换为后缀表达式。在实际处理过程中，我们通过扫描中缀表达式中每一个字符，然后进行相应的操作。
示例说明2：计算后缀表达式的值
以下为一个简单的例子：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 100
typedef enum {
OP_PLUS = '+',
OP_MINUS = '-',
OP_MULTIPLY = '*',
OP_DIVIDE = '/',
OP_LEFT_PARENTHESES = '(',
OP_RIGHT_PARENTHESES = ')',
OP_END = '\0'
} operator;
typedef struct {
int* top;
int* stack;
int size;
} integer_stack;
void integer_push(integer_stack* stack, int value) {
if (stack->top - stack->stack >= stack->size) {
printf("stack is full\n");
return;
}
*(++stack->top) = value;
}
int integer_pop(integer_stack* stack) {
if (stack->top == stack->stack) {
printf("stack is empty\n");
return 0;
}
return *(stack->top--);
}
int integer_top(integer_stack* stack) {
if (stack->top == stack->stack) {
printf("stack is empty\n");
return 0;
}
return *(stack->top);
}
integer_stack* integer_stack_create(int size) {
integer_stack* stack = (integer_stack*) malloc(sizeof(integer_stack));
stack->top = stack->stack - 1;
stack->stack = (int*) malloc(sizeof(int) * size);
stack->size = size;
return stack;
}
void integer_stack_destroy(integer_stack* stack) {
free(stack->stack);
stack->stack = NULL;
stack->top = NULL;
stack->size = 0;
free(stack);
}
int is_number(char ch) {
return ch >= '0' && ch <= '9';
}
int is_operator(char ch) {
return ch == '+' || ch == '-' || ch == '*' || ch == '/';
}
int apply_operator(int left, int right, operator op) {
switch (op) {
case OP_PLUS:
return left + right;
case OP_MINUS:
return left - right;
case OP_MULTIPLY:
return left * right;
case OP_DIVIDE:
return left / right;
default:
printf("invalid operator\n");
return 0;
}
}
int evaluate_postfix(char* postfix) {
integer_stack* stack = integer_stack_create(strlen(postfix) + 1);
int i = 0;
while (postfix[i] != '\0') {
char ch = postfix[i++];
if (is_number(ch)) {
integer_push(stack, ch - '0');
} else if (is_operator(ch)) {
int right = integer_pop(stack);
int left = integer_pop(stack);
integer_push(stack, apply_operator(left, right, ch));
} else {
printf("invalid character: %c\n", ch);
}
}
int result = integer_pop(stack);
integer_stack_destroy(stack);
return result;
}
int main() {
char postfix[MAXSIZE] = "345*67+/8-";
int result = evaluate_postfix(postfix);
printf("postfix: %s\nresult: %d\n", postfix, result);
return 0;
}
在上面的示例代码中，我们定义了一个整数栈来维护后缀表达式求值的过程。其中integer_push、integer_pop和integer_top函数是操作栈的基本函数。apply_operator函数用来计算两个操作数的运算结果。evaluate_postfix函数用来计算后缀表达式的值。在实际处理过程中，我们通过扫描后缀表达式中每一个字符，然后进行相应的操作。
本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：C语言实现逆波兰式实例 - Python技术站
微信扫一扫 
支付宝扫一扫 