C语言之波兰表达式、逆波兰表达式和普通表达式
C语言之表达式、波兰表达式、逆波兰表达式
表达式的格式
- 这里只用双目运算符加+、减-、乘*、除/和一位数0-9，这样更简单便于理解！
- 普通表达式，运算符在中间，也称中缀表达式，如： 8+3*4， (2+3)*9
- 波兰表达式，运算符在前面，也称前缀表达式，如： +8*34， *+239
- 逆波兰表达式，运算符在后面，也称后缀表达式，如： 834*+， 23+9*
- 普通（中缀）表达式需要圆括号，波兰（前缀）表达式和逆波兰（后缀）表达式则不需要括号！！！
普通表达式的运算规则
- 圆括号优先，先算括号内的表达式；
- 乘除运算优先于加减运算，也就是说乘除运算的优先级高于加减运算；
- 同级别的运算，先算左侧，再算右侧；
表达式的转换
- 普通表达式转换为波兰表达式过程如下所示：
8+3*4 | (2+3)*9
a = 3*4 | a = 2+3
a = *34 | a = +23
8+a | a*9
+8a | *a9
+8*34 | *+239
- 普通表达式转换为逆波兰表达式过程如下所示：
8+3*4 | (2+3)*9
a = 3*4 | a = 2+3
a = 34* | a = 23+
8+a | a*9
8a+ | a9*
834*+ | 23+9*
逆波兰表达式的求值
- 逆波兰表达式更易于计算机理解，求值方法也更简单：
- 从左至右读取表达式
- 如果是数字，则入栈
- 如果是运算符，则从栈中弹出数字，运算，再将结果入栈
- 如此循环，最后栈底数字即为表达式的值，栈的状态如下所示：
rpn express : 45+7-
------------------------------------------
4 5 + 7 -
| | | | | | | | | | | | | |
| | |5| | | | | |7| | | | |
|4| |4| | | |9| |9| | | |2|
------------------------------------------
- 用字符数组模拟一个栈，求逆波兰表达式的值，代码如下：
/* filename : eval.c */
#include <stdio.h>
/* compile : gcc eval.c -o eval */
/* run : ./eval */
/* evalute rpn express */
char
eval_rpn (char *expr)
{
int rs = 0;
char buf[32] = {0};
char idx = 0, ip = 0;
char c = expr[idx];
while (c != 0)
{
switch (c)
{
case '0'...'9': //number
buf[ip] = c - '0'; ip++;
printf ("push %c\n", c);
break;
case '+': case '-': case '*': case '/': //operator
{
char a = buf[ip-2];
char b = buf[ip-1];
char it, *op;
if (c == '+') { it = a + b; op = "add"; }
else if (c == '-') { it = a - b; op = "sub"; }
else if (c == '*') { it = a * b; op = "mul"; }
else if (c == '/') { it = a / b; op = "add"; }
buf[ip-2] = it;
buf[ip-1] = 0; ip--;
printf ("operate %s : %d %c %d ==> %d\n", op, a, c, b, it);
}
break;
default:
printf ("Syntax error!\n");
}
idx++; c = expr[idx];
}
rs = buf[0];
return rs;
}
/* test function */
void
test_eval_rpn (void)
{
//char *rst = "834*+"; //=20
char *rst = "982/-23*5*+"; //=37
int rs;
printf ("RPN : [%s]\n", rst);
printf ("--------------------\n");
rs = eval_rpn (rst);
printf ("--------------------\n");
printf ("Result : %d\n", rs);
}
/**/
int
main (int argc, char *argv[])
{
test_eval_rpn ();
return 0;
}
/***(.(.(.(.))))***/
编译运行，结果如下：
songvm@ubuntu:~/works/xdn/boo$ gcc eval.c -o eval
songvm@ubuntu:~/works/xdn/boo$ ./eval
RPN : [834*+]
--------------------
push 8
push 3
push 4
operate mul : 3 * 4 ==> 12
operate add : 8 + 12 ==> 20
--------------------
Result : 20
songvm@ubuntu:~/works/xdn/boo$
注意表达式的值不能大于+127或小于-127，否则值是不准确的！！！
- 因为字符是单字节的，取值范围在正负127之间！
- 再运算一个稍复杂的表达式，结果如下：
songvm@ubuntu:~/works/xdn/boo$ gcc eval.c -o eval
songvm@ubuntu:~/works/xdn/boo$ ./eval
RPN : [982/-23*5*+]
--------------------
push 9
push 8
push 2
operate add : 8 / 2 ==> 4
operate sub : 9 - 4 ==> 5
push 2
push 3
operate mul : 2 * 3 ==> 6
push 5
operate mul : 6 * 5 ==> 30
operate add : 5 + 30 ==> 35
--------------------
Result : 35
songvm@ubuntu:~/works/xdn/boo$
波兰表达式的求值
- 第一种方法是将波兰表达式逆序求值，从右向左读取计算；
- 第二种方法是将表达式字符串倒过来用上面的逆波兰表达式求值函数eval_rpn来计算；
- 方便起见，用第二种方法，代码如下：
/* evalute pn express */
char
eval_pn (char *expr)
{
char rst[128] = {0};
char c, rs;
int len = 0;
while (expr[len] != 0)
len++;
for (int i=len-1, j=0; i >= 0; i--, j++)
rst[j] = expr[i];
printf ("RPN : [%s]\n", rst);
printf ("--------------------\n");
rs = eval_rpn (rst);
return rs;
}
/* test evalute pn express function */
void
test_eval_pn (void)
{
//char *pst = "+7*45"; // =27
char *pst = "+*9*22-/395"; //=38
char rs;
printf ("PN : [%s]\n", pst);
rs = eval_pn (pst);
printf ("--------------------\n");
printf ("Result : %d\n", rs);
}
编译运行，测试简单的波兰表达式，结果如下：
songvm@ubuntu:~/works/xdn/boo$ gcc eval.c -o eval
songvm@ubuntu:~/works/xdn/boo$ ./eval
PN : [+7*45]
RPN : [54*7+]
--------------------
push 5
push 4
operate mul : 5 * 4 ==> 20
push 7
operate add : 20 + 7 ==> 27
--------------------
Result : 27
songvm@ubuntu:~/works/xdn/boo$
再测试一个复杂一点的波兰表达式，结果如下：
songvm@ubuntu:~/works/xdn/boo$ gcc eval.c -o eval
songvm@ubuntu:~/works/xdn/boo$ ./eval
PN : [+*9*22-/395]
RPN : [593/-22*9*+]
--------------------
push 5
push 9
push 3
operate add : 9 / 3 ==> 3
operate sub : 5 - 3 ==> 2
push 2
push 2
operate mul : 2 * 2 ==> 4
push 9
operate mul : 4 * 9 ==> 36
operate add : 2 + 36 ==> 38
--------------------
Result : 38
songvm@ubuntu:~/works/xdn/boo$
用递归方法求波兰表达式的值
- 力扣网站有一个用递归方法求波兰表达式的值的问题
- 仿照他的方法，编写一个函数eval_pnr，代码如下：
/* define RS datatype */
typedef struct _Result RS;
struct _Result {
int result;
int n;
};
/* evaluate pn express use recursion */
RS
eval_pnr (char *expr)
{
RS rs = {0,0};
RS ra, rb;
if (*expr == 0) return rs;
if (expr[0] >= '0' && expr[0] <= '9')
{
rs.result = expr[0]-'0';
rs.n = 1;
return rs;
}
ra = eval_pnr (expr + 1);
rb = eval_pnr (expr + ra.n + 1);
if(expr[0] == '+') rs.result = ra.result + rb.result;
if(expr[0] == '-') rs.result = ra.result - rb.result;
if(expr[0] == '*') rs.result = ra.result * rb.result;
if(expr[0] == '/') rs.result = ra.result - rb.result;
printf ("operate : %d %c %d = %d\n",
ra.result, expr[0], rb.result, rs.result);
rs.n = 1 + ra.n + rb.n;
return rs;
}
/* test evaluate pn express use recursion */
void
test_eval_pnr (void)
{
char *expr = "+*35-*246"; //=17
RS tmp;
printf ("PN : [%s]\n", expr);
printf ("--------------------\n");
tmp = eval_pnr (expr);
printf ("--------------------\n");
printf ("Result : %d\n", tmp.result);
}
编译运行，测试一个复杂的表达式，效果如下：
songvm@ubuntu:~/works/xdn/boo$ gcc eval.c -o eval
songvm@ubuntu:~/works/xdn/boo$ ./eval
PN : [+*35-*246]
--------------------
operate : 3 * 5 = 15
operate : 2 * 4 = 8
operate : 8 - 6 = 2
operate : 15 + 2 = 17
--------------------
Result : 17
songvm@ubuntu:~/works/xdn/boo$
基本达到预期，完整代码如下：
/* filename : eval.c */
#include <stdio.h>
/* compile : gcc eval.c -o eval */
/* run : ./eval */
/* evalute rpn express */
char
eval_rpn (char *expr)
{
int rs = 0;
char buf[32] = {0};
char idx = 0, ip = 0;
char c = expr[idx];
while (c != 0)
{
switch (c)
{
case '0'...'9': //number
buf[ip] = c - '0'; ip++;
printf ("push %c\n", c);
break;
case '+': case '-': case '*': case '/': //operator
{
char a = buf[ip-2];
char b = buf[ip-1];
char it, *op;
if (c == '+') { it = a + b; op = "add"; }
else if (c == '-') { it = a - b; op = "sub"; }
else if (c == '*') { it = a * b; op = "mul"; }
else if (c == '/') { it = a / b; op = "add"; }
buf[ip-2] = it;
buf[ip-1] = 0; ip--;
printf ("operate %s : %d %c %d ==> %d\n", op, a, c, b, it);
}
break;
default:
printf ("Syntax error!\n");
}
idx++; c = expr[idx];
}
rs = buf[0];
return rs;
}
/* test evalut rpn express function */
void
test_eval_rpn (void)
{
//char *rst = "834*+"; //=20
char *rst = "982/-23*5*+"; //=37
int rs;
printf ("RPN : [%s]\n", rst);
printf ("--------------------\n");
rs = eval_rpn (rst);
printf ("--------------------\n");
printf ("Result : %d\n", rs);
}
/* evalute pn express */
char
eval_pn (char *expr)
{
char rst[128] = {0};
char c, rs;
int len = 0;
while (expr[len] != 0)
len++;
for (int i=len-1, j=0; i >= 0; i--, j++)
rst[j] = expr[i];
printf ("RPN : [%s]\n", rst);
printf ("--------------------\n");
rs = eval_rpn (rst);
return rs;
}
/* test evalute pn express function */
void
test_eval_pn (void)
{
//char *pst = "+7*45"; // =27
char *pst = "+*9*22-/395"; //=38
char rs;
printf ("PN : [%s]\n", pst);
rs = eval_pn (pst);
printf ("--------------------\n");
printf ("Result : %d\n", rs);
}
/* define RS datatype */
typedef struct _Result RS;
struct _Result {
int result;
int n;
};
/* evaluate pn express use recursion */
RS
eval_pnr (char *expr)
{
RS rs = {0,0};
RS ra, rb;
if (*expr == 0) return rs;
if (expr[0] >= '0' && expr[0] <= '9')
{
rs.result = expr[0]-'0';
rs.n = 1;
return rs;
}
ra = eval_pnr (expr + 1);
rb = eval_pnr (expr + ra.n + 1);
if(expr[0] == '+') rs.result = ra.result + rb.result;
if(expr[0] == '-') rs.result = ra.result - rb.result;
if(expr[0] == '*') rs.result = ra.result * rb.result;
if(expr[0] == '/') rs.result = ra.result - rb.result;
printf ("operate : %d %c %d = %d\n",
ra.result, expr[0], rb.result, rs.result);
rs.n = 1 + ra.n + rb.n;
return rs;
}
/* test evaluate pn express use recursion */
void
test_eval_pnr (void)
{
char *expr = "+*35-*246"; //=17
RS tmp;
printf ("PN : [%s]\n", expr);
printf ("--------------------\n");
tmp = eval_pnr (expr);
printf ("--------------------\n");
printf ("Result : %d\n", tmp.result);
}
/**/
int
main (int argc, char *argv[])
{
//test_eval_rpn ();
//test_eval_pn ();
test_eval_pnr ();
return 0;
}
/***(.(.(.(.))))***/
普通表达式如何求值
- 办法就是将普通表达式转换为波兰表达式，然后求值即可！！！
下一步研究如何将普通表达式（中缀表达式）转换为前缀表达式或后缀表达式的！
原文地址：https://blog.csdn.net/gwsong52/article/details/143737973
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！