C语言之用链表的方式解析与运算简单的波兰表达式
我这里说的简单的波兰表达式，是指没有嵌套的加减乘除表达式，
如： (+ 1 2)， (- 100 90 5)
定义基本的数据结构
- 定义数据类型，全用大写字母，DT开头，后面附加类型名字：DT_OPERATOR
- 定义表达式结构体，Express，自定义为Expr
- 定义链表节点结构体，ExpressNode，自定义为ExprNode
- 定义逐项遍历操作用到的函数指针EPFunc
代码如下：
/* define express datatype */
#define DT_OPERATOR 0X01
#define DT_INTEGER 0X02
/* define express struct */
typedef struct _Express Expr;
struct _Express {
char dt; //express datatype
union {
char oval; //operator
long ival; //integer
} V;
};
/* define express node struct */
typedef struct _ExpressNode ExprNode;
struct _ExpressNode {
Expr expr;
ExprNode *next;
};
/* define function pointer for express node */
typedef void (*EPFunc) (Expr expr);
实现链表的基本功能：创建、释放、追加、逐项
- 创建节点函数，创建运算符节点：expr_node_new_op，创建整数节点：expr_node_new_int
- 释放节点函数 expr_node_free
- 追加节点函数 expr_node_append
- 逐项遍历函数 expr_node_foreach
代码如下：
/* create a new operator express node */
ExprNode *
expr_node_new_op (char val)
{
ExprNode *node = (ExprNode*) malloc (sizeof(ExprNode));
node->expr.dt = DT_OPERATOR;
node->expr.V.oval = val;
node->next = NULL;
return node;
}
/* create a new integer express node */
ExprNode *
expr_node_new_int (long val)
{
ExprNode *node = (ExprNode*) malloc (sizeof(ExprNode));
node->expr.dt = DT_INTEGER;
node->expr.V.ival = val;
node->next = NULL;
return node;
}
/* free the express node list */
void
expr_node_free (ExprNode *node)
{
while (node != NULL)
{
ExprNode *tmp = node->next;
free (node);
node = tmp;
}
}
/* append node to head */
ExprNode *
expr_node_append (ExprNode *head, ExprNode *node)
{
ExprNode *tmp = head;
if (tmp == NULL) return node;
while (tmp->next != NULL)
tmp = tmp->next;
tmp->next = node;
return head;
}
/* foreach node call epfunc from head to end */
void
expr_node_foreach (ExprNode *head, EPFunc epfunc)
{
ExprNode *tmp = head;
while (tmp != NULL)
{
epfunc (tmp->expr);
tmp = tmp->next;
}
}
实现基本的运算功能：加、减、乘、除
- 加法运算函数：expr_node_opadd
- 减法运算函数：expr_node_opsub
- 乘法运算函数：expr_node_opmul
- 除法运算函数：expr_node_opdiv
代码如下：
/* compute express list */
/* declare here */
long
expr_node_compute (ExprNode *head);
/* run operator + return long int */
static long
expr_node_opadd (ExprNode *node)
{
long rs = 0;
ExprNode *tmp = node;
if (tmp == NULL) return rs; //(+) return 0
if (tmp->expr.dt == DT_INTEGER)
{ rs = tmp->expr.V.ival; }
tmp = tmp->next;
while (tmp != NULL)
{
if (tmp->expr.dt == DT_INTEGER)
{
rs = rs + tmp->expr.V.ival;
}
tmp = tmp->next;
}
//printf ("OP add, RS : %ld\n", rs);
return rs;
}
/* run operator - return long int */
static long
expr_node_opsub (ExprNode *node)
{
long rs = 0;
ExprNode *tmp = node;
if (tmp == NULL) return rs; //(-) ??? out err info
if (tmp->expr.dt == DT_INTEGER)
{ rs = tmp->expr.V.ival; }
tmp = tmp->next;
if (tmp == NULL) return -rs; //(- 9) ==> -9
while (tmp != NULL)
{
if (tmp->expr.dt == DT_INTEGER)
{
rs = rs - tmp->expr.V.ival;
}
tmp = tmp->next;
}
//printf ("OP sub, RS : %ld\n", rs);
return rs;
}
/* run operator * return long int */
static long
expr_node_opmul (ExprNode *node)
{
long rs = 0;
ExprNode *tmp = node;
if (tmp == NULL) return 1; //(*) return 1;
if (tmp->expr.dt == DT_INTEGER)
{ rs = tmp->expr.V.ival; }
tmp = tmp->next;
while (tmp != NULL)
{
if (tmp->expr.dt == DT_INTEGER)
{
rs = rs * tmp->expr.V.ival;
}
tmp = tmp->next;
}
//printf ("OP mul, RS : %ld\n", rs);
return rs;
}
/* run operator / return long int */
static long
expr_node_opdiv (ExprNode *node)
{
long rs = 1;
ExprNode *tmp = node;
if (tmp == NULL) return rs; //(/) ??? out err info
if (tmp->expr.dt == DT_INTEGER)
{ rs = tmp->expr.V.ival; }
tmp = tmp->next;
while (tmp != NULL)
{
if (tmp->expr.dt == DT_INTEGER)
{
rs = rs / tmp->expr.V.ival;
}
tmp = tmp->next;
}
//printf ("OP div, RS : %ld\n", rs);
return rs;
}
/* compute express list */
long
expr_node_compute (ExprNode *node)
{
long rs = 0;
ExprNode *tmp = node;
switch (tmp->expr.V.oval)
{
case '+': rs = expr_node_opadd (tmp->next); break;
case '-': rs = expr_node_opsub (tmp->next); break;
case '*': rs = expr_node_opmul (tmp->next); break;
case '/': rs = expr_node_opdiv (tmp->next); break;
}
return rs;
}
实现基本的信息输出功能，输出值和输出类型、值
- 输出值函数：out_expr_value
- 输出类型和值函数：out_expr_info
- 输出表达式函数：out_express
- 输出表达式信息函数：out_expinfo
代码如下：
/* declare out_expinfo */
void
out_expinfo (ExprNode *head);
/* declare out_express */
void
out_express (ExprNode *head);
/* output express info */
void
out_expr_info (Expr expr)
{
switch (expr.dt)
{
case DT_OPERATOR: printf (" OP: %c\n", expr.V.oval); break;
case DT_INTEGER : printf ("INT: %ld\n", expr.V.ival); break;
}
}
/* output express value */
void
out_expr_value (Expr expr)
{
switch (expr.dt)
{
case DT_OPERATOR: printf (" %c", expr.V.oval); break;
case DT_INTEGER : printf (" %ld", expr.V.ival); break;
}
}
/* output full express info */
void
out_expinfo (ExprNode *head)
{
expr_node_foreach (head, out_expr_info);
}
/* output full express value */
void
out_express (ExprNode *head)
{
printf (" (");
expr_node_foreach (head, out_expr_value);
printf (" )");
}
解析波兰表达式，将各个节点存入链表
- 宏定义NBSIZE，指定保存数字的数组长度，即数的位数
- parse_expr_string函数的参数是波兰表达式字符串
- 返回值是链表节点指针
代码如下：
/* define number length */
#define NBSIZE 32
/* parse express string to express node */
ExprNode *
parse_expr_string (char *estr)
{
ExprNode *root = NULL;
char nbuf[NBSIZE] = {0};
int idx = 0, ndx = 1, lv = 0;
char c;
nbuf[0] = '+'; //default +
c = estr[idx];
while (c != 0)
{
switch (c)
{
case '0'...'9': //number
{
char n = estr[idx+1];
nbuf[ndx] = c; ndx++;
if (n == ' ' || n == ')')
{
long lt = strtol (nbuf, NULL, 10);
ExprNode *tmp = expr_node_new_int (lt);
root = expr_node_append (root, tmp);
memset (nbuf, 0, NBSIZE); nbuf[0] = '+'; ndx = 1;
}
}
break;
case '+': case '-': case '*': case '/': //operator
{
if (c == '+' || c == '-')
{
char n = estr[idx+1];
if (n >= '0' && n <= '9')
{
nbuf[0] = c; break;
}
}
ExprNode *tmp = expr_node_new_op (c);
root = expr_node_append (root, tmp);
}
break;
case '(':
{ lv++; } //todo
break;
case ')':
{
lv--;
if (lv == 0) { return root; } //todo
}
break;
case ' ': //space
break;
defualt:
printf ("Error: Syntax error!\n");
}
idx++; c = estr[idx];
}
return root;
}
测试解析加法波兰表达式字符串函数
代码如下：
/* test function */
void
test_parse (void)
{
//char *str = "(+ 10 20 30 40 50)";
//char *str = "(+ 2 3 4)";
//char *str = "(+ 2 3)";
//char *str = "(+ 2)";
//char *str = "(/)"; //out err info, need arg
//char *str = "(*)"; //return 1
//char *str = "(-)"; //out err info, need arg
char *str = "(+)"; //return 0
ExprNode *head;
head = parse_expr_string (str);
printf (" express : %s\n", str);
printf ("-------------------------\n");
out_expinfo (head);
printf ("-------------------------\n");
printf ("full expr:");
out_express (head);
printf ("\n-------------------------\n");
printf ("Result : %ld\n", expr_node_compute (head));
expr_node_free (head);
}
/**/
int
main (int argc, char *argv[])
{
test_parse ();
return 0;
}
//-----(+ 1 2)-----//
编译运行，结果如下：
gwsong@ubuntu:~/works/notes/lisp$ gcc xa.c -o xa
gwsong@ubuntu:~/works/notes/lisp$ ./xa
express : (+ 10 20 30 40 50)
-------------------------
OP: +
INT: 10
INT: 20
INT: 30
INT: 40
INT: 50
-------------------------
full expr: ( + 10 20 30 40 50 )
-------------------------
Result : 150
gwsong@ubuntu:~/works/notes/lisp$ gcc xa.c -o xa
gwsong@ubuntu:~/works/notes/lisp$ ./xa
express : (+ 2 3 4)
-------------------------
OP: +
INT: 2
INT: 3
INT: 4
-------------------------
full expr: ( + 2 3 4 )
-------------------------
Result : 9
gwsong@ubuntu:~/works/notes/lisp$ gcc xa.c -o xa
gwsong@ubuntu:~/works/notes/lisp$ ./xa
express : (+ 2 3)
-------------------------
OP: +
INT: 2
INT: 3
-------------------------
full expr: ( + 2 3 )
-------------------------
Result : 5
gwsong@ubuntu:~/works/notes/lisp$ gcc xa.c -o xa
gwsong@ubuntu:~/works/notes/lisp$ ./xa
express : (+ 2)
-------------------------
OP: +
INT: 2
-------------------------
full expr: ( + 2 )
-------------------------
Result : 2
gwsong@ubuntu:~/works/notes/lisp$ gcc xa.c -o xa
gwsong@ubuntu:~/works/notes/lisp$ ./xa
express : (+)
-------------------------
OP: +
-------------------------
full expr: ( + )
-------------------------
Result : 0
gwsong@ubuntu:~/works/notes/lisp$
测试解析减法波兰表达式字符串
字符串定义如下：
//char *str = "(- 1000 500 100 50 10 5)";
//char *str = "(- 10 5 1)";
//char *str = "(- 3 2)";
char *str = "(- 3)";
//char *str = "(-)"; //out err info, need arg
编译运行，结果如下：
gwsong@ubuntu:~/works/notes/lisp$ gcc xa.c -o xa
gwsong@ubuntu:~/works/notes/lisp$ ./xa
express : (- 1000 500 100 50 10 5)
-------------------------
OP: -
INT: 1000
INT: 500
INT: 100
INT: 50
INT: 10
INT: 5
-------------------------
full expr: ( - 1000 500 100 50 10 5 )
-------------------------
Result : 335
gwsong@ubuntu:~/works/notes/lisp$ gcc xa.c -o xa
gwsong@ubuntu:~/works/notes/lisp$ ./xa
express : (- 10 5 1)
-------------------------
OP: -
INT: 10
INT: 5
INT: 1
-------------------------
full expr: ( - 10 5 1 )
-------------------------
Result : 4
gwsong@ubuntu:~/works/notes/lisp$ gcc xa.c -o xa
gwsong@ubuntu:~/works/notes/lisp$ ./xa
express : (- 3 2)
-------------------------
OP: -
INT: 3
INT: 2
-------------------------
full expr: ( - 3 2 )
-------------------------
Result : 1
gwsong@ubuntu:~/works/notes/lisp$ gcc xa.c -o xa
gwsong@ubuntu:~/works/notes/lisp$ ./xa
express : (- 3)
-------------------------
OP: -
INT: 3
-------------------------
full expr: ( - 3 )
-------------------------
Result : -3
gwsong@ubuntu:~/works/notes/lisp$
- 只测试了加减法，只有减号时没有提示信息，以后还要完善，包含两个数：分数和复数！！！
- 下一步研究一下波兰表达式嵌套问题，这样的： (+ 1 (+ 2 3)) ！！！
完整代码如下：
/* filename: xa.c */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* compile : gcc xa.c -o xa */
/* run : ./xa */
/* define express datatype */
#define DT_OPERATOR 0X01
#define DT_INTEGER 0X02
/* define express struct */
typedef struct _Express Expr;
struct _Express {
char dt; //express datatype
union {
char oval; //operator
long ival; //integer
} V;
};
/* define express node struct */
typedef struct _ExpressNode ExprNode;
struct _ExpressNode {
Expr expr;
ExprNode *next;
};
/* define function pointer for express node */
typedef void (*EPFunc) (Expr expr);
/* create a new operator express node */
ExprNode *
expr_node_new_op (char val)
{
ExprNode *node = (ExprNode*) malloc (sizeof(ExprNode));
node->expr.dt = DT_OPERATOR;
node->expr.V.oval = val;
node->next = NULL;
return node;
}
/* create a new integer express node */
ExprNode *
expr_node_new_int (long val)
{
ExprNode *node = (ExprNode*) malloc (sizeof(ExprNode));
node->expr.dt = DT_INTEGER;
node->expr.V.ival = val;
node->next = NULL;
return node;
}
/* free the express node list */
void
expr_node_free (ExprNode *node)
{
while (node != NULL)
{
ExprNode *tmp = node->next;
free (node);
node = tmp;
}
}
/* append node to head */
ExprNode *
expr_node_append (ExprNode *head, ExprNode *node)
{
ExprNode *tmp = head;
if (tmp == NULL) return node;
while (tmp->next != NULL)
tmp = tmp->next;
tmp->next = node;
return head;
}
/* foreach node call epfunc from head to end */
void
expr_node_foreach (ExprNode *head, EPFunc epfunc)
{
ExprNode *tmp = head;
while (tmp != NULL)
{
epfunc (tmp->expr);
tmp = tmp->next;
}
}
/* compute express list */
/* declare here */
long
expr_node_compute (ExprNode *head);
/* run operator + return long int */
static long
expr_node_opadd (ExprNode *node)
{
long rs = 0;
ExprNode *tmp = node;
if (tmp == NULL) return rs; //(+) return 0
if (tmp->expr.dt == DT_INTEGER)
{ rs = tmp->expr.V.ival; }
tmp = tmp->next;
while (tmp != NULL)
{
if (tmp->expr.dt == DT_INTEGER)
{
rs = rs + tmp->expr.V.ival;
}
tmp = tmp->next;
}
//printf ("OP add, RS : %ld\n", rs);
return rs;
}
/* run operator - return long int */
static long
expr_node_opsub (ExprNode *node)
{
long rs = 0;
ExprNode *tmp = node;
if (tmp == NULL) return rs; //(-) ??? out err info
if (tmp->expr.dt == DT_INTEGER)
{ rs = tmp->expr.V.ival; }
tmp = tmp->next;
if (tmp == NULL) return -rs; //(- 9) ==> -9
while (tmp != NULL)
{
if (tmp->expr.dt == DT_INTEGER)
{
rs = rs - tmp->expr.V.ival;
}
tmp = tmp->next;
}
//printf ("OP sub, RS : %ld\n", rs);
return rs;
}
/* run operator * return long int */
static long
expr_node_opmul (ExprNode *node)
{
long rs = 0;
ExprNode *tmp = node;
if (tmp == NULL) return 1; //(*) return 1;
if (tmp->expr.dt == DT_INTEGER)
{ rs = tmp->expr.V.ival; }
tmp = tmp->next;
while (tmp != NULL)
{
if (tmp->expr.dt == DT_INTEGER)
{
rs = rs * tmp->expr.V.ival;
}
tmp = tmp->next;
}
//printf ("OP mul, RS : %ld\n", rs);
return rs;
}
/* run operator / return long int */
static long
expr_node_opdiv (ExprNode *node)
{
long rs = 1;
ExprNode *tmp = node;
if (tmp == NULL) return rs; //(/) ??? out err info
if (tmp->expr.dt == DT_INTEGER)
{ rs = tmp->expr.V.ival; }
tmp = tmp->next;
while (tmp != NULL)
{
if (tmp->expr.dt == DT_INTEGER)
{
rs = rs / tmp->expr.V.ival;
}
tmp = tmp->next;
}
//printf ("OP div, RS : %ld\n", rs);
return rs;
}
/* compute express list */
long
expr_node_compute (ExprNode *node)
{
long rs = 0;
ExprNode *tmp = node;
switch (tmp->expr.V.oval)
{
case '+': rs = expr_node_opadd (tmp->next); break;
case '-': rs = expr_node_opsub (tmp->next); break;
case '*': rs = expr_node_opmul (tmp->next); break;
case '/': rs = expr_node_opdiv (tmp->next); break;
}
return rs;
}
/* declare out_expinfo */
void
out_expinfo (ExprNode *head);
/* declare out_express */
void
out_express (ExprNode *head);
/* output express info */
void
out_expr_info (Expr expr)
{
switch (expr.dt)
{
case DT_OPERATOR: printf (" OP: %c\n", expr.V.oval); break;
case DT_INTEGER : printf ("INT: %ld\n", expr.V.ival); break;
}
}
/* output express value */
void
out_expr_value (Expr expr)
{
switch (expr.dt)
{
case DT_OPERATOR: printf (" %c", expr.V.oval); break;
case DT_INTEGER : printf (" %ld", expr.V.ival); break;
}
}
/* output full express info */
void
out_expinfo (ExprNode *head)
{
expr_node_foreach (head, out_expr_info);
}
/* output full express value */
void
out_express (ExprNode *head)
{
printf (" (");
expr_node_foreach (head, out_expr_value);
printf (" )");
}
/* define number length */
#define NBSIZE 32
/* parse express string to express node */
ExprNode *
parse_expr_string (char *estr)
{
ExprNode *root = NULL;
char nbuf[NBSIZE] = {0};
int idx = 0, ndx = 1, lv = 0;
char c;
nbuf[0] = '+'; //default +
c = estr[idx];
while (c != 0)
{
switch (c)
{
case '0'...'9': //number
{
char n = estr[idx+1];
nbuf[ndx] = c; ndx++;
if (n == ' ' || n == ')')
{
long lt = strtol (nbuf, NULL, 10);
ExprNode *tmp = expr_node_new_int (lt);
root = expr_node_append (root, tmp);
memset (nbuf, 0, NBSIZE); nbuf[0] = '+'; ndx = 1;
}
}
break;
case '+': case '-': case '*': case '/': //operator
{
if (c == '+' || c == '-')
{
char n = estr[idx+1];
if (n >= '0' && n <= '9')
{
nbuf[0] = c; break;
}
}
ExprNode *tmp = expr_node_new_op (c);
root = expr_node_append (root, tmp);
}
break;
case '(':
{ lv++; } //todo
break;
case ')':
{
lv--;
if (lv == 0) { return root; } //todo
}
break;
case ' ': //space
break;
defualt:
printf ("Error: Syntax error!\n");
}
idx++; c = estr[idx];
}
return root;
}
/* test function */
void
test_parse (void)
{
//char *str = "(+ 10 20 30 40 50)";
//char *str = "(+ 2 3 4)";
//char *str = "(+ 2 3)";
//char *str = "(+ 2)";
//char *str = "(/)"; //out err info, need arg
//char *str = "(*)"; //return 1
//char *str = "(-)"; //out err info, need arg
//char *str = "(+)"; //return 0
//char *str = "(- 1000 500 100 50 10 5)";
//char *str = "(- 10 5 1)";
//char *str = "(- 3 2)";
char *str = "(- 3)";
ExprNode *head;
head = parse_expr_string (str);
printf (" express : %s\n", str);
printf ("-------------------------\n");
out_expinfo (head);
printf ("-------------------------\n");
printf ("full expr:");
out_express (head);
printf ("\n-------------------------\n");
printf ("Result : %ld\n", expr_node_compute (head));
expr_node_free (head);
}
/**/
int
main (int argc, char *argv[])
{
test_parse ();
return 0;
}
//-----(+ 1 2)-----//