主体程序：
/* calc_expr.c */
/************************************************************************
*
* 计算中序表达式demo程序
* nizqsut
************************************************************************/
#include
#include
#include "../libdc/stackar.h"
#include "../libdc/fatal.h"
#include "../include/expression.h"
static char infix[] = "a+b*c+(d*e+f)*g";
static char subfix[sizeof(infix)+1];
//static const char digitals[] = {'1','2','3',''
//}
static TOKEN_PRIO get_token_prio(char token){
TOKEN_PRIO token_prio;
if (is_digital(token)) {
return DIGITAL;
}
if (is_char(token)) {
return CH_TOKEN;
}
switch(token) {
case '+':
case '-':
token_prio = ADD_SUB;
break;
case '*':
case '/':
token_prio = MULTI_DIV;
break;
case '(':
token_prio = LEFT_BRACKET;
break;
case ')':
token_prio = RIGHT_BRACKET;
break;
default:
token_prio = UNKOWN_TOKEN;
}
return token_prio;
}
int expr_input(char *buf_in, int buf_len){
char ch;
int in_len;
in_len = 0;
while ( (ch = getchar()) != 0x0a ) {
buf_in[in_len++] = ch;
if (in_len == (buf_len - 1)) {
Error("Goto max input!\n");
return -1;
}
}
buf_in[in_len] = 0;
return 0;
}
/* 将字符串表达式转化为中缀表达式 */
int string2infix(char *str, TOKEN *tokens, int max_token){
int value;
//int token_cnt;
TOKEN_PRIO token_prio;
TOKEN_PRIO old_token_prio;
old_token_prio = UNKOWN_TOKEN;
//token_cnt = 0;
value = 0;
while (*str) {
switch( (token_prio = get_token_prio(*str) ) ) {
case DIGITAL:
value *= 10;
value += ch_to_dig(*str);
old_token_prio = token_prio;
break;
case ADD_SUB:
case MULTI_DIV:
case LEFT_BRACKET:
case RIGHT_BRACKET:
if (DIGITAL == old_token_prio) {
if ( !tokens) {
Error("Not tokens for use!");
return -1;
}
tokens->prio = DIGITAL;
tokens->value = value;
value = 0;
// tokens = tokens->next;
tokens++;
}
if ( !tokens) {
Error("Not tokens for use!");
return -1;
}
tokens->prio = token_prio;
tokens->value = *str;
//tokens = tokens->next;
tokens++;
break;
default:
Error("Unkown token type!");
return -1;
}
str++;
old_token_prio = token_prio;
}
if (DIGITAL == old_token_prio) {
if ( !tokens) {
Error("Not tokens for use!");
return -1;
}
tokens->prio = DIGITAL;
tokens->value = value;
}
return 0;
}
static void out2subfix(char ch){
static int subfix_index = 0;
subfix[subfix_index++] = ch;
}
static void token_copy(TOKEN *src, TOKEN *target){
target->prio = src->prio;
target->value = src->value;
}
/* 将中缀表达式编程后缀表达式 */
int infix2subfix(TOKEN *infix_token, TOKEN *subfix_token, STACK_OP stack_op){
//STACK_OP stack_op;
// TOKEN_PRIO token_prio;
// TOKEN_PRIO last_token_prio;
TOKEN token;
stack_op->make_empty(stack_op);
while (infix_token->prio != UNKOWN_TOKEN) {
switch( infix_token->prio) {
case DIGITAL:
//case CH_TOKEN:
//out2subfix(infix[i++]);
//if (subfix_token) {
token_copy(infix_token,subfix_token++);
//subfix_token = subfix_token->next;
//subfix_token++;
//}else{
// Error("Subfix token flow!");
// return -1;
//}
break;
case MULTI_DIV:
case ADD_SUB:
while (1) {
if (stack_op->is_empty(stack_op)) {
stack_op->push(stack_op, *infix_token);
break;
}else{
/* 如果栈里面的操作符优先级比当前操作符优先级高或相等，则其弹出栈 */
if ( (stack_op->get_top(stack_op)).prio >= infix_token->prio ) {
//if (subfix_token) {
token = stack_op->pop(stack_op);
token_copy(&token, subfix_token++);
//token_copy( &(stack_op->pop(stack_op)), subfix_token++);
// subfix_token = subfix_token->next;
//}else{
// Error("Subfix token flow!");
// return -1;
//}
}else{
stack_op->push(stack_op,*infix_token);
break;
}
}
}
break;
case LEFT_BRACKET:
stack_op->push(stack_op,*infix_token);
break;
case RIGHT_BRACKET:
do {
if ( LEFT_BRACKET == (stack_op->get_top(stack_op)).prio ) {
stack_op->pop(stack_op);
break;
}
//if (subfix_token) {
token = stack_op->pop(stack_op);
token_copy(&token, subfix_token++);
//token_copy( &stack_op->pop(stack_op), subfix_token++);
// subfix_token = subfix_token->next;
//}else{
// Error("Subfix token flow!");
// return -1;
//}
} while(1);
break;
default:
Error("Unkown token prio!\n");
break;
}
infix_token++;
//infix_token = infix_token->next;
}
while (!stack_op->is_empty(stack_op)) {
//if (subfix_token) {
//token = stack_op->get_top(stack_op);
token = stack_op->pop(stack_op);
token_copy(&token, subfix_token++);
//token_copy( &stack_op->pop(stack_op), subfix_token++);
// subfix_token = subfix_token->next;
//}else{
// Error("Subfix token flow!");
// return -1;
//}
//out2subfix(stack_op->pop(stack_op));
}
/* subfix 结束标志为 prio == UNKOWN_TOKEN*/
subfix_token->prio = UNKOWN_TOKEN;
return 0;
}
static int
calc_token(TOKEN *token, int operater, int operator){
int result;
switch(token->prio) {
case ADD_SUB:
case MULTI_DIV:
break;
default:
Error("Unkown operater type!");
// return -1;
break;
}
switch(token->value) {
case '+':
result = operater + operator;
break;
case '-':
result = operater - operator;
break;
case '*':
result = operater * operator;
break;
case '/':
result = operater / operator;
break;
default:
//Error("Unkown operator value!");
//return -1;
break;
}
return result;
}
/************************************************************************/
/* 计算后缀表达式方法: */
/* 遇到操作数，压栈；遇到操作符，弹出需要的操作数做运算 */
/************************************************************************/
int calc_subfix(TOKEN *subfix, STACK_OP stack_op){
int operater; //操作数
int operator; //被操作数
TOKEN token;
stack_op->make_empty(stack_op);
while (subfix->prio != UNKOWN_TOKEN) {
switch(subfix->prio) {
case DIGITAL:
stack_op->push(stack_op, *subfix);
break;
case ADD_SUB:
case MULTI_DIV:
operator = stack_op->pop(stack_op).value;
operater = stack_op->pop(stack_op).value;
token.value = calc_token(subfix,operater,operator);
token.prio = DIGITAL;
stack_op->push(stack_op,token);
break;
default:
Error("Unkown token type!");
break;
}
subfix++;
}
if ( !stack_op->is_empty(stack_op)) {
token = stack_op->pop(stack_op);
printf("Expression value equal:%d\n",token.value);
}else{
Error("Subfix error!");
return -1;
}
return 0;
}
#define EXPR_INPUT_BUF_LEN 256
#define MAX_TOKEN 16
/*
"a+b*c+(d*e+f)*g"的后缀表达式为：
a b c * + d e * f + g * +
"3+5*6+(18*24+17)/12" 后最表达式为：
3 5 6 * + 18 24 * 17 + 12 / +
*/
int calc_expr(void){
char buf_in[EXPR_INPUT_BUF_LEN]; //= "3+5*6+(18*24+17)/12";// = "11+12*13+(14*15+16)*17";
STACK_OP stack_op;
TOKEN infix[MAX_TOKEN];
TOKEN subfix[MAX_TOKEN];
int i;
if ( !(stack_op = stack_init(MAX_TOKEN)) ) {
Error("Stack initial fail!");
goto exit_calc_expr;
}
/*
if ( !(infix = malloc(sizeof(struct TOKEN) * MAX_TOKEN)) ) {
Error("Out of space!");
goto free_stack_mem;
}
if ( !(subfix = malloc(sizeof(struct TOKEN) * MAX_TOKEN)) ) {
Error("Out of space!");
goto free_infix_mem;
}*/
for (i = 0; i < MAX_TOKEN; i++) {
infix[i].prio = UNKOWN_TOKEN;
subfix[i].prio = UNKOWN_TOKEN;
}
if (expr_input(buf_in,EXPR_INPUT_BUF_LEN)) {
Error("Expression input error!");
goto free_all_mem;
}/**/
if (string2infix(buf_in,infix,MAX_TOKEN)) {
Error("String2infix error!");
goto free_all_mem;
}
if (infix2subfix(infix,subfix,stack_op)) {
Error("infix2subfix error!");
goto free_all_mem;
}
if (calc_subfix(subfix,stack_op)) {
}
free_all_mem:
// free(subfix);
//free_infix_mem:
// free(infix);
//free_stack_mem:
stack_release(stack_op);
exit_calc_expr:
return 0;
}
//----------------------------------------------------------------------------
表达式相应的头文件：
/* expression.h */
#ifndef __EXPRESSION_H__
#define __EXPRESSION_H__
#define true 1
#define false 0
#define is_digital(c) ( ((c) >= '0') && ((c) <= '9') ) ? true : false
#define is_char(c) ( ((c) >= 'a') && ((c) <= 'z') ) ? true : false
#define ch_to_dig(ch) ( (ch) - '0' )
typedef enum {
UNKOWN_TOKEN = 0,
LEFT_BRACKET,
RIGHT_BRACKET,
DIGITAL,
CH_TOKEN,
ADD_SUB,
MULTI_DIV,
// LEFT_BRACKET,
// RIGHT_BRACKET,
}TOKEN_PRIO;
typedef struct TOKEN{
int value;
TOKEN_PRIO prio;
//TOKEN *next;
}TOKEN;
//----------------------------------------------------------------------------
堆栈头文件：
/* stackar.h */
#ifndef __STACKAR_H__
#define __STACKAR_H__
/* 打开边界检查功能 */
#define STACK_DEBUG
#define MIN_STACK_SIZE 8
#define EMPTY_TOS -1
#define STACK_TRUE 1
#define STACK_FALSE 0
#define EXPR_STACK
//--
//#ifndef element_type
//#ifdef EXPR_STACK
#include "../include/expression.h"
typedef struct TOKEN element_type;
//#else
//typedef int element_type;
//#endif
//#endif
//--
typedef struct _STACK_OP *STACK_OP;
struct _STACK_OP{
void *priv;
void (*make_empty)(STACK_OP stack_op);
int (*is_full)(STACK_OP stack_op);
int (*is_empty)(STACK_OP stack_op);
void (*push)(STACK_OP stack_op, element_type element);
element_type (*pop)(STACK_OP stack_op);
element_type (*get_top)(STACK_OP stack_op);
int (*get_capacity)(STACK_OP stack_op);
}_STACK_OP;
STACK_OP stack_init(int stack_capacity);
void stack_release(STACK_OP stack_op);
#endif
//----------------------------------------------------------------------------
堆栈的实现：
/* stackar.c */
#include "stackar.h"
#include "fatal.h"
struct _STACK_INFO {
int capacity;
int top_pos; // top of stack
element_type *array;
}_STACK_INFO;
typedef struct _STACK_INFO *STACK_INFO;
static void make_empty(STACK_OP stack_op){
STACK_INFO stack_info;
stack_info = stack_op->priv;
stack_info->top_pos = EMPTY_TOS;
}
/* If stack is full return STACK_TRUE, else return STACK_FALSE. */
static int is_full(STACK_OP stack_op){
STACK_INFO stack_info;
stack_info = stack_op->priv;
return ( (stack_info->top_pos + 1) == stack_info->capacity ) ? STACK_TRUE : STACK_FALSE;
}
/* If stack is empty return STACK_TRUE, else return STACK_FALSE. */
static int is_empty(STACK_OP stack_op){
STACK_INFO stack_info;
stack_info = stack_op->priv;
return (stack_info->top_pos == EMPTY_TOS) ? STACK_TRUE : STACK_FALSE;
}
/* 先栈指针加一，再入栈。属于满栈 */
static void push(STACK_OP stack_op, element_type element){
STACK_INFO stack_info;
stack_info = stack_op->priv;
#ifdef STACK_DEBUG
if (STACK_TRUE == stack_op->is_full(stack_op)) {
Error("Stack have full. Can't push!");
return;
}
#endif
stack_info->array[++stack_info->top_pos] = element;
return;
}
/* 先出栈，再使栈指针减一 */
static element_type pop(STACK_OP stack_op){
STACK_INFO stack_info;
element_type element;
stack_info = stack_op->priv;
#ifdef STACK_DEBUG
if (STACK_TRUE == stack_op->is_empty(stack_op)) {
Error("Stack is empty. Cann't pop!");
//return ; /* avoid complier warning. */
}
#endif
element = stack_info->array[stack_info->top_pos];
stack_info->top_pos--;
return element;
//return stack_info->array[stack_info->top_pos--];
}
/* 返回栈顶元素 */
static element_type get_top(STACK_OP stack_op){
STACK_INFO stack_info;
stack_info = stack_op->priv;
return stack_info->array[stack_info->top_pos];
}
/* 返回整个栈容量 */
static int get_capacity(STACK_OP stack_op){
STACK_INFO stack_info;
stack_info = stack_op->priv;
return stack_info->capacity;
}
/* 分配栈所需要的内存，初始化栈操作的函数指针
* 如果初始化失败返回空指针
*/
STACK_OP stack_init(int stack_capacity){
STACK_INFO stack_info;
STACK_OP stack_op;
if (stack_capacity < MIN_STACK_SIZE) {
Error("Stack size is too small");
}
if ( !(stack_op = malloc(sizeof *stack_op)) ) {
Error("Out of space!!");
goto error_exit;
}
if ( !(stack_info = malloc(sizeof(*stack_info))) ) {
Error("Out of space!!");
goto free_stack_op;
}
if (!(stack_info->array=(element_type *)malloc( sizeof(element_type) * stack_capacity))) {
Error("Out of space!!");
goto free_stack_info;
}
stack_info->capacity = stack_capacity;
stack_op->priv = (void *)stack_info;
stack_op->make_empty = make_empty;
stack_op->push = push;
stack_op->pop = pop;
stack_op->is_empty = is_empty;
stack_op->is_full = is_full;
stack_op->get_capacity = get_capacity;
stack_op->get_top = get_top;
stack_op->make_empty(stack_op);
return stack_op;
free_stack_info:
free(stack_info);
free_stack_op:
free(stack_op);
error_exit:
return NULL;
}
void stack_release(STACK_OP stack_op){
STACK_INFO stack_info;
stack_op->make_empty(stack_op);
stack_info = stack_op->priv;
free(stack_info->array);
free(stack_info);
free(stack_op);
return;
}
阅读(1358) | 评论(0) | 转发(0) |
