C语言之中缀表达式转换为波兰表达式、逆波兰表达式

🕗 发布于 2024-11-15 14:49 c语言 开发语言 算法 数据结构

C语言之中缀表达式转换为波兰表达式、逆波兰表达式

这篇博文：波兰表达式与逆波兰表达式，文章中详细的说明了如何将中缀表达式转换为前缀表达式和后缀表达式的。

中缀表达式转换为波兰（前缀）表达式的逻辑过程如下：

建立一个符号栈，并从右至左遍历表达式；
若遍历到数，则直接输出；
若遍历到右括号’)'，直接压入栈顶（括号优先级最高，入栈时不比较）
若遇到左括号’(‘，表明括号已结束，不断弹出栈顶运算符并输出，直至弹出右括号’)'，但该右括号只弹出不输出（相当于抵消左右括号，将其之间的运算符弹出并输出）；
若遇到其他运算符：
** 栈为空时，直接入栈；
** 若栈顶元素为右括号’)‘，直接入栈；
** 若栈顶为其他运算符，则比较其优先级：（注意此处优先级比较与后缀表达式的不同）
*** 若优先级大于等于栈顶，则直接入栈；
*** 若优先级小于栈顶，弹出栈顶并输出，然后不断与新的栈顶比较，直至优先级大于等于栈顶或栈空或栈顶为右括号’)'，再将该运算符入栈；
** 表达式遍历完毕，弹出符号栈内剩余所有运算符并输出，再逆序输出结果字符串，即为前缀表达式。

C语言代码实现上述过程

宏定义栈的高度，#define STSIZE 8
宏定义输出跟踪信息，OUT_TRACE，分别输出表达式字符串的索引、字符、符号栈的指针值、符号栈的内容，输出表达式的内容！
定义获取运算符优先级函数get_plv，加减法＋－的优先级为1，乘除法＊／的优先级为2。
中缀转前缀功能函数mid_topn，参数est为中缀表达式字符串，参数buf为保存前缀表达式的字符指针，参数size为buf的长度。
在函数中定义字符数组st[STSIZE]模拟符号栈来压入或弹出中缀表达式的字符，ip为栈指针！
在函数中定义表达式字符串的索引idx，输出表达式的索引jdx！
先循环计数求出表达式字符串的长度，idx从len-1开始计数，至0结束！
buf最后要逆序输出，也就是将字符串倒转一下！
调用mid_topn函数参数buf一定要初始化为0，以保证结果正确：char buf[128] = {0};

代码如下：

/* filename: topn.c */
#include <stdio.h>

/* compile : gcc topn.c -o topn */
/*     run : ./topn             */

/* define stack size */
#define STSIZE 8

/* output trace info */
#define OUT_TRACE() \
  printf ("%2d, [%c], %d, [", idx, c, ip);\
  for (int k = 0; k < STSIZE; k++)\
    if (st[k] != 0)\
      printf ("%c", st[k]);\
    else \
      printf (" ");\
  printf ("]|[%s]\n", buf)

/* get priority level */
char
get_plv (char x)
{
  if (x == '+') return 1;
  if (x == '-') return 1;
  if (x == '*') return 2;
  if (x == '/') return 2;
  return 0;
}

/* mid to pn express */
void
mid_topn (char *estr, char *buf, int size)
{
  char st[STSIZE] = {0}, ip = 0;
  char len = 0, idx, jdx = 0, c;
  while (estr[len] != 0)
    len++;
  idx = len - 1;
  c = estr[idx]; //right -> left
  while (idx >= 0)
    {
      switch (c)
{
case '0'...'9': //number
  buf[jdx] = c; jdx++;  //out
  break;

case '+': case '-': case '*': case '/': //operator
  {
    char lv, lx;
    if (ip == 0)
      { st[ip] = c; ip++; break; } //push
    if (st[ip-1] == ')')
      { st[ip] = c; ip++; break; } //push
    lv = get_plv (c);
    lx = get_plv (st[ip-1]);
    if (lv >= lx)
      { st[ip] = c; ip++; break; } //push
    else
      {
buf[jdx] = st[ip-1]; jdx++; //out
st[ip-1] = 0; ip--; //pop
while (ip > 0)
  {
    char lt = get_plv (st[ip-1]);
    if (lv >= lt)
      { st[ip] = c; ip++; break; } //push
    else
      {
buf[jdx] = st[ip-1]; jdx++; //out
st[ip-1] = 0; ip--; //pop
      }
  }
if (ip == 0)
  { st[ip] = c; ip++; break;} //push
      }
  }
  break;

case ')': //
  st[ip] = c; ip++; //push
  break;

case '(': //
  {
    while (ip > 0)
      {
char ot = st[ip-1];
if (ot == ')')
  {
    st[ip-1] = 0; ip--; break; //pop
  }
else
  {
    buf[jdx] = st[ip-1]; jdx++; //out
    st[ip-1] = 0; ip--; //pop
  }
      }
  }
  break;

default:
  printf ("Syntax error!\n");
}

      OUT_TRACE();
      idx--; c = estr[idx]; //prev char
    }

  //pop until stack empty
  for (char i = STSIZE - 1; i >= 0; i--)
    {
      if (st[i] != 0)
{
  buf[jdx] = st[i]; jdx++; //pop
  printf ("%2d, [%c], %d, [        ]|[%s]\n", i, st[i], i, buf);
}
    }

  //reverse buf
  for (char i = 0, j = jdx-1; i < jdx/2; i++, j--)
    {
      char tmp = buf[i]; buf[i] = buf[j]; buf[j] = tmp;
    }
}

/* test mid_topn function */
void
test_topn (void)
{
  //char *est = "1+2+3";
  //char *est = "9-5-2";
  //char *est = "1+2-3";
  //char *est = "1-2+3";
  //char *est = "1*2";
  //char *est = "1*2*3";
  //char *est = "1/2";
  //char *est = "1/2/3";
  //char *est = "1+2*3*4";
  char *est = "1+2*3*4-5";
  //char *est = "1*2+3";
  //char *est = "1+2*3";
  //char *est = "1+2*3+4";
  //char *est = "1-2/3-4";
  //char *est = "1*2+3*4";
  //char *est = "1*2-3*4";
  //char *est = "9-8/7+6*5-4*3";
  //char *est = "9*(8+7)";
  //char *est = "9-(8*(2+7)/3)";
  
  char buf[128] = {0};

  printf ("Express : [%s]\n", est);
  printf ("--------------------\n");
  mid_topn (est, buf, 128);
  printf ("--------------------\n");
  printf ("PN expr : [%s]\n", buf);
}

/**/
int
main (int argc, char *argv[])
{
  test_topn ();
  return 0;
}
/****(x())****/

编译运行，达到预期，结果如下：

songvm@ubuntu:~/works/xdn/boo/exp$ gcc topn.c -o topn
songvm@ubuntu:~/works/xdn/boo/exp$ ./topn
Express : [1+2*3*4-5]
--------------------
 8, [5], 0, [        ]|[5]
 7, [-], 1, [-       ]|[5]
 6, [4], 1, [-       ]|[54]
 5, [*], 2, [-*      ]|[54]
 4, [3], 2, [-*      ]|[543]
 3, [*], 3, [-**     ]|[543]
 2, [2], 3, [-**     ]|[5432]
 1, [+], 2, [-+      ]|[5432**]
 0, [1], 2, [-+      ]|[5432**1]
 1, [+], 1, [        ]|[5432**1+]
 0, [-], 0, [        ]|[5432**1+-]
--------------------
PN expr : [-+1**2345]
songvm@ubuntu:~/works/xdn/boo/exp$

中缀表达式转换为逆波兰（后缀）表达式逻辑过程如下：

建立一个符号栈，并从左至右遍历表达式；
若遍历到数，则直接输出；
若遍历到左括号’('，直接压入栈顶（括号优先级最高，入栈时不比较）；
若遇到右括号’)‘，则说明括号已结束，不断弹出栈顶运算符并输出，直至弹出左括号’('，但该左括号只弹出不输出（相当于抵消左右括号，将其之间的运算符弹出并输出）；
若遇到其他运算符：
** 栈为空时，直接入栈；
** 若栈顶元素为左括号’(‘，直接入栈；
** 若栈顶为其他运算符，则比较其优先级：（注意此处优先级比较与前缀表达式的不同）
*** 若优先级大于栈顶，则直接入栈；
*** 若优先级小于等于栈顶，弹出栈顶并输出，然后不断与新的栈顶比较，直至优先级大于栈顶或栈空或栈顶为左括号’('，再将该运算符入栈；
** 表达式遍历完毕，弹出符号栈内剩余所有运算符并输出，结果字符串即为后缀表达式。

用C语言来实现上述过程

定义函数mid_torpn，函数的主体结构与topn函数基本相同，只需要注意优先级比较与前缀表达式的不同
idx是从0开始计算！！！
保存结果的buf不用逆序了！！！

代码如下：

/* filename: torpn.c */
#include <stdio.h>

/* compile : gcc torpn.c -o torpn */
/*     run : ./torpn              */

/* define stack size */
#define STSIZE 8

/* output trace info */
#define OUT_TRACE() \
  printf ("%2d, [%c], %d, [", idx, c, ip);\
  for (int k = 0; k < STSIZE; k++)\
    if (st[k] != 0)\
      printf ("%c", st[k]);\
    else \
      printf (" ");\
  printf ("]|[%s]\n", buf)

/* get priority level */
char
get_plv (char x)
{
  if (x == '+') return 1;
  if (x == '-') return 1;
  if (x == '*') return 2;
  if (x == '/') return 2;
  return 0;
}

/* mid to rpn express */
void
mid_torpn (char *estr, char *buf, int size)
{
  char st[STSIZE] = {0}, ip = 0;
  char idx = 0, jdx = 0, c;

  c = estr[idx]; //left -> right
  while (c != 0)
    {
      switch (c)
{
case '0'...'9': //number
  buf[jdx] = c; jdx++;  //out
  break;

case '+': case '-': case '*': case '/': //operator
  {
    char lv, lx;
    if (ip == 0)
      { st[ip] = c; ip++; break; } //push
    if (st[ip-1] == '(')
      { st[ip] = c; ip++; break; } //push
    lv = get_plv (c);
    lx = get_plv (st[ip-1]);
    if (lv > lx)
      { st[ip] = c; ip++; break; } //push
    else
      {
buf[jdx] = st[ip-1]; jdx++; //out
st[ip-1] = 0; ip--; //pop
while (ip > 0)
  {
    char lt = get_plv (st[ip-1]);
    if (lv > lt)
      { st[ip] = c; ip++; break; } //push
    else
      {
buf[jdx] = st[ip-1]; jdx++; //out
st[ip-1] = 0; ip--; //pop
      }
  }
if (ip == 0)
  { st[ip] = c; ip++; break;} //push
      }
  }
  break;

case '(': //
  st[ip] = c; ip++; //push
  break;

case ')': //
  {
    while (ip > 0)
      {
char ot = st[ip-1];
if (ot == '(')
  {
    st[ip-1] = 0; ip--; break; //pop
  }
else
  {
    buf[jdx] = st[ip-1]; jdx++; //out
    st[ip-1] = 0; ip--; //pop
  }
      }
  }
  break;

default:
  printf ("Syntax error!\n");
}

      OUT_TRACE();
      idx++; c = estr[idx]; //next char
    }

  //pop until stack empty
  for (char i = STSIZE - 1; i >= 0; i--)
    {
      if (st[i] != 0)
{
  buf[jdx] = st[i]; jdx++; //out
  printf ("%2d, [%c], %d, [        ]|[%s]\n", i, st[i], i, buf);
}
    }
}

/* test mid_torpn function */
void
test_torpn (void)
{
  //char *est = "1+2";
  //char *est = "1+2+3";
  //char *est = "1+2+3+4";
  //char *est = "1+2+3+4+5";
  //char *est = "1*2";
  //char *est = "1*2*3";
  //char *est = "1*2*3*4";
  //char *est = "1*2*3*4*5";
  //char *est = "1+2*3*4";
  //char *est = "1+2*3*4-5";
  //char *est = "5*(1+2)";
  //char *est = "(1+2)*5";
  //char *est = "(1+2)*(3+4)";
  char *est = "9-(1*(2+3)-4)+5";

  char buf[128] = {0};

  printf ("Express : [%s]\n", est);
  printf ("--------------------\n");
  mid_torpn (est, buf, 128);
  printf ("--------------------\n");
  printf ("PN expr : [%s]\n", buf);
}

/**/
int
main (int argc, char *argv[])
{
  test_torpn ();
  return 0;
}
/****(()x)****/

编译运行，达到预期，结果如下：

songvm@ubuntu:~/works/xdn/boo/exp$ gcc torpn.c -o torpn
songvm@ubuntu:~/works/xdn/boo/exp$ ./torpn
Express : [9-(1*(2+3)-4)+5]
--------------------
 0, [9], 0, [        ]|[9]
 1, [-], 1, [-       ]|[9]
 2, [(], 2, [-(      ]|[9]
 3, [1], 2, [-(      ]|[91]
 4, [*], 3, [-(*     ]|[91]
 5, [(], 4, [-(*(    ]|[91]
 6, [2], 4, [-(*(    ]|[912]
 7, [+], 5, [-(*(+   ]|[912]
 8, [3], 5, [-(*(+   ]|[9123]
 9, [)], 3, [-(*     ]|[9123+]
10, [-], 3, [-(-     ]|[9123+*]
11, [4], 3, [-(-     ]|[9123+*4]
12, [)], 1, [-       ]|[9123+*4-]
13, [+], 1, [+       ]|[9123+*4--]
14, [5], 1, [+       ]|[9123+*4--5]
 0, [+], 0, [        ]|[9123+*4--5+]
--------------------
PN expr : [9123+*4--5+]
songvm@ubuntu:~/works/xdn/boo/exp$

完成普通表达式和波兰表达式的转换，用上一篇文章的求值函数，就可以实现普通表达式的求值计算了。

以上关于表达式的编码都是演示性的，有局限（字符型、只能计算个位数），不具备实用功能！下一步研究如何计算长整型数，使其具有实用性！！！

原文地址：https://blog.csdn.net/gwsong52/article/details/143786287

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：【鸿蒙开发】第二十一章 Location位置服务
下一篇：PGMP-练练03 ❥(^_-)

设计模式之装饰器模式(SSO单点登录功能扩展，增加拦截用户访问方法范围场景)
不改变原有类，可能有的小伙伴会想到继承、AOP切面，当然这些方式都可以实现，但是使用装饰器模式会是另外一种思路更为灵活，可以避免继承导致的子类过多，也可以避免AOP带来的复杂性。就像夏天热你穿短裤，冬
阅读更多2024-11-15
MySQL45讲第二十三讲是怎么保证数据不丢的？
在 MySQL 的世界里，数据的可靠性是至关重要的。今天，我们将深入探讨 MySQL 是如何保证数据不丢的，这涉及到 binlog 和 redo log 的写入机制，以及一些关键参数的设置。
阅读更多2024-11-15
【Electron】Electron Forge如何支持Element plus？
在 Electron Forge 项目中集成 Element Plus 是一个相对直接的过程。Element Plus 是一个基于 Vue 3 的 UI 组件库，因此你需要确保你的 Electron
阅读更多2024-11-15
jupyter可视化pandas dataframe
在Jupyter中显示HTML表格。
阅读更多2024-11-15
如何使用Jupyter
Jupyter Notebook 是一个开源的 Web 应用程序，允许你创建和共享包含实时代码、方程、可视化和解释性文本的文档。Jupyter Notebook 还支持许多高级功能，如魔法命令、扩展、
阅读更多2024-11-15
利用飞书多维表格自动发布版本
飞书的多维表格有自动化的能力，我们每周只需要设定好版本发布的时间，可以让其自动触发版本发布，并在群里通知所有人。那么假定我们每隔10分钟获取一次，除非在发版前10分钟内修改发版计划，否则都能感知到版本
阅读更多2024-11-15
SQL Server Service Broker完整示例
SQL server Service Broker实战
阅读更多2024-11-15
QT鼠标事件
这篇文章介绍如何使用事件和获取事件的信号。
阅读更多2024-11-15
基于Python+Vue开发的旅游景区管理系统
该项目是基于Python+Vue开发的旅游景区管理系统（前后端分离），这是一项为大学生课程设计作业而开发的项目。该系统旨在帮助大学生学习并掌握Python编程技能，同时锻炼他们的项目设计与开发能力。通
阅读更多2024-11-15
2023年12月中国电子学会青少年软件编程（Python）等级考试试卷（三级）答案 + 解析
2023年12月中国电子学会青少年软件编程（Python）等级考试试卷（三级）答案 + 解析
阅读更多2024-11-15

C语言之中缀表达式转换为波兰表达式、逆波兰表达式

C语言之中缀表达式转换为波兰表达式、逆波兰表达式

中缀表达式转换为波兰（前缀）表达式的逻辑过程如下：

C语言代码实现上述过程

编译运行，达到预期，结果如下：

中缀表达式转换为逆波兰（后缀）表达式逻辑过程如下：

用C语言来实现上述过程

编译运行，达到预期，结果如下：

完成普通表达式和波兰表达式的转换，用上一篇文章的求值函数，就可以实现普通表达式的求值计算了。

相关文章