C语言实现中缀表达式转换为后缀表达式

本文实例为大家分享了C语言实现中缀表达式转后缀表达式的具体代码,供大家参考,具体内容如下

中缀表达式转换为后缀表达式(思路)

1.创建栈

2.从左向右顺序获取中缀表达式

a.数字直接输出
b.运算符

情况一:遇到左括号直接入栈,遇到右括号将栈中左括号之后入栈的运算符全部弹栈输出,同时左括号出栈但是不输出。

情况二:遇到乘号和除号直接入栈,直到遇到优先级比它更低的运算符,依次弹栈。

情况三:遇到加号和减号,如果此时栈空,则直接入栈,否则,将栈中优先级高的运算符依次弹栈(注意:加号和减号属于同一个优先级,所以也依次弹栈)直到栈空或则遇到左括号为止,停止弹栈。(因为左括号要匹配右括号时才弹出)。

情况四:获取完后,将栈中剩余的运算符号依次弹栈输出

例:比如将:2*(9+6/3-5)+4转化为后缀表达式 2 9 6 3 / +5 - * 4 +

转换算法代码如下:

/*中缀转后缀函数*/
void Change(SqStack *S,Elemtype str[])
{
 int i=0;
 Elemtype e;
 InitStack(S);
 while(str[i]!='\0')
 {
 while(isdigit(str[i]))
 {/*过滤数字字符,直接输出,直到下一位不是数字字符打印空格跳出循环 */
 printf("%c",str[i++]);
 if(!isdigit(str[i]))
 {
 printf(" ");
 }
 }
 /*加减运算符优先级最低,如果栈顶元素为空则直接入栈,否则将栈中存储
 的运算符全部弹栈,如果遇到左括号则停止,将弹出的左括号从新压栈,因为左
 括号要和又括号匹配时弹出,这个后面单独讨论。弹出后将优先级低的运算符压入栈中*/
 if(str[i]=='+'||str[i]=='-')
 {
 if(!StackLength(S))
 {
 PushStack(S,str[i]);
 }
 else
 {
 do
 {
  PopStack(S,&e);
  if(e=='(')
  {
  PushStack(S,e);
  }
  else
  {
  printf("%c ",e);
  }
 }while( StackLength(S) && e != '(' );

 PushStack(S,str[i]);
 }
 }
 /*当遇到右括号是,把括号里剩余的运算符弹出,直到匹配到左括号为止
 左括号只弹出不打印(右括号也不压栈)*/
 else if(str[i]==')')
 {
 PopStack(S,&e);
 while(e!='(')
 {
 printf("%c ",e);
 PopStack(S,&e);
 }
 }
 /*乘、除、左括号都是优先级高的,直接压栈*/
 else if(str[i]=='*'||str[i]=='/'||str[i]=='(')
 {
 PushStack(S,str[i]);
 }

 else if(str[i]=='\0')
 {
 break;
 }

 else
 {
 printf("\n输入格式错误!\n");
 return ;
 }
 i++;
 }
 /*最后把栈中剩余的运算符依次弹栈打印*/
 while(StackLength(S))
 {
 PopStack(S,&e);
 printf("%c ",e);
 }
}

完整代码如下:

#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<assert.h>

#define INITSIZE 20
#define INCREMENT 10
#define MAXBUFFER 20
#define LEN sizeof(Elemtype)

/*栈的动态分配存储结构*/
typedef char Elemtype;
typedef struct{
 Elemtype *base;
 Elemtype *top;
 int StackSize;
}SqStack;

/*初始化栈*/
void InitStack(SqStack *S)
{
 S->base=(Elemtype*)malloc(LEN*INITSIZE);
 assert(S->base !=NULL);
 S->top=S->base;
 S->StackSize=INITSIZE;
}

/*压栈操作*/
void PushStack(SqStack *S,Elemtype c)
{
 if(S->top - S->base >= S->StackSize)
 {
 S->base=(Elemtype*)realloc(S->base,LEN*(S->StackSize+INCREMENT));
 assert(S->base !=NULL);
 S->top =S->base+S->StackSize;
 S->StackSize+=INCREMENT;
 }
 *S->top++ = c;
}
/*求栈长*/
int StackLength(SqStack *S)
{
 return (S->top - S->base);
}
/*弹栈操作*/
int PopStack(SqStack *S,Elemtype *c)
{
 if(!StackLength(S))
 {
 return 0;
 }
 *c=*--S->top;
 return 1;
}

/*中缀转后缀函数*/
void Change(SqStack *S,Elemtype str[])
{
 int i=0;
 Elemtype e;
 InitStack(S);
 while(str[i]!='\0')
 {
 while(isdigit(str[i]))
 {/*过滤数字字符,直接输出,直到下一位不是数字字符打印空格跳出循环 */
 printf("%c",str[i++]);
 if(!isdigit(str[i]))
 {
 printf(" ");
 }
 }
 /*加减运算符优先级最低,如果栈顶元素为空则直接入栈,否则将栈中存储
 的运算符全部弹栈,如果遇到左括号则停止,将弹出的左括号从新压栈,因为左
 括号要和又括号匹配时弹出,这个后面单独讨论。弹出后将优先级低的运算符压入栈中*/
 if(str[i]=='+'||str[i]=='-')
 {
 if(!StackLength(S))
 {
 PushStack(S,str[i]);
 }
 else
 {
 do
 {
  PopStack(S,&e);
  if(e=='(')
  {
  PushStack(S,e);
  }
  else
  {
  printf("%c ",e);
  }
 }while( StackLength(S) && e != '(' );

 PushStack(S,str[i]);
 }
 }
 /*当遇到右括号是,把括号里剩余的运算符弹出,直到匹配到左括号为止
 左括号只弹出不打印(右括号也不压栈)*/
 else if(str[i]==')')
 {
 PopStack(S,&e);
 while(e!='(')
 {
 printf("%c ",e);
 PopStack(S,&e);
 }
 }
 /*乘、除、左括号都是优先级高的,直接压栈*/
 else if(str[i]=='*'||str[i]=='/'||str[i]=='(')
 {
 PushStack(S,str[i]);
 }

 else if(str[i]=='\0')
 {
 break;
 }

 else
 {
 printf("\n输入格式错误!\n");
 return ;
 }
 i++;
 }
 /*最后把栈中剩余的运算符依次弹栈打印*/
 while(StackLength(S))
 {
 PopStack(S,&e);
 printf("%c ",e);
 }
}

int main()
{
 Elemtype str[MAXBUFFER];
 SqStack S;
 gets(str);
 Change(&S,str);
 return 0;
}

运行效果截图如下:

如何实现将中缀表达式转换成后缀表达式后计算值

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • C++中缀表达式转后缀表达式的方法

    本文实例为大家分享了C++中缀表达式转后缀表达式的具体代码,供大家参考,具体内容如下 1.初始化两个栈:运算符栈s1和储存中间结果的栈s2: 2.从左至右扫描中缀表达式: 3.遇到操作数时,将其压s2: 4.遇到运算符时,比较其与s1栈顶运算符的优先级: 1).如果s1为空,或栈顶运算符为左括号"(",则直接将此运算符入栈: 2).否则,若优先级比栈顶运算符的高,也将运算符压入s1 3).否则,将s1栈顶的运算符弹出并压入到s2中,再次转到(4-1)与s1中新的栈顶运算符相比较: 5.

  • C++实现中缀表达式转后缀表达式

    本文实例为大家分享了C++实现中缀表达式转后缀表达式的具体代码,供大家参考,具体内容如下 一.思路:和中缀表达式的计算类似,只不过不用计算,把表达式输出即可 1.用字符数组存储整行输入的中缀表达式: 2.接着从字符数组的0位置开始判断字符,如果是数字,那就要判断后面是否是数字,如果是就不断扫描组成一个整数 (暂不考虑负数和小数),最终组成一个整数,然后输出这个数(因为不用计算,所以直接输出即可): 3.如果是左括号,直接进符号栈: 4.如果是操作运算符,与符号栈的栈顶元素比较优先级:如果高就压入

  • C++利用栈实现中缀表达式转后缀表达式

    本文实例为大家分享了C++实现中缀表达式转后缀表达式的具体代码,供大家参考,具体内容如下 题目:现有中缀表达式如:1+(2-3)*4+10/5 请用栈的特性编写一个程序,使得程序输出后缀表达式 分析如下: STEP1: 1+(2-3)*4+10/5 首先遇到第一个输入是数字1,数字在后缀表达式中都是直接输出,接着是符号"+",入栈: STEP2: 1+(2-3)*4+10/5 第三个字符是"(",依然是符号,入栈,接着是数字2,输出,然后是符号"-&quo

  • C语言实现中缀表达式转换为后缀表达式

    本文实例为大家分享了C语言实现中缀表达式转后缀表达式的具体代码,供大家参考,具体内容如下 中缀表达式转换为后缀表达式(思路) 1.创建栈 2.从左向右顺序获取中缀表达式 a.数字直接输出 b.运算符 情况一:遇到左括号直接入栈,遇到右括号将栈中左括号之后入栈的运算符全部弹栈输出,同时左括号出栈但是不输出. 情况二:遇到乘号和除号直接入栈,直到遇到优先级比它更低的运算符,依次弹栈. 情况三:遇到加号和减号,如果此时栈空,则直接入栈,否则,将栈中优先级高的运算符依次弹栈(注意:加号和减号属于同一个优

  • C语言利用栈实现对后缀表达式的求解

    本文实例为大家分享了C语言实现对后缀表达式(逆波兰表达式)的求解代码,供大家参考,具体内容如下 逆波兰表达式: 逆波兰表达式又叫后缀表达式.它是由相应的语法树的后序遍历的结果得到的. 例:5 - 8*(6 + 7) + 9 / 4: 其中缀表达式为:5 - 8 * 6 + 7 + 9 / 4 其语法树如下: 因此根据语法树可以得出他后序遍历(后缀表达式)为: 5 8 6 7 + * - 9 4 / + 这样就实现了中缀表达式到后缀表达式的转换. 同样的也可以得出他的前序遍历(前缀表达式也称波兰表

  • java数据结构与算法之中缀表达式转为后缀表达式的方法

    本文实例讲述了java数据结构与算法之中缀表达式转为后缀表达式的方法.分享给大家供大家参考,具体如下: //stack public class StackX { private int top; private char[] stackArray; private int maxSize; //constructor public StackX(int maxSize){ this.maxSize = maxSize; this.top = -1; stackArray = new char[

  • Java中缀表达式转后缀表达式实现方法详解

    本文实例讲述了Java中缀表达式转后缀表达式实现方法.分享给大家供大家参考,具体如下: 本文先给出思路与方法,最后将给出完整代码 项目实战: https://www.jb51.net/article/158335.htm 算法综述: 一.中缀表达式转后缀表达式: 1.中缀表达式要转后缀表达式,首先需要两个Stack(栈),其中一个应用于存放字符,另一个用于存放数字. 2.读到数字直接存入数字栈中,读到字符时,要咸鱼栈内前一元素(字符)进行比较,当当前(要存入的字符)优先级大于迁移字符时才存入,否

  • Java中缀表达式转后缀表达式流程详解

    目录 一.栈 1.栈的基本介绍 2.栈的底层实现 二.中缀表达式转后缀表达式 1.拆解中缀表达式 2.中缀转后缀的算法 3.中缀转后缀代码解析 4.对后缀表达式进行计算 一.栈 1.栈的基本介绍 栈是⼀个先⼊后出的有序列表.栈(stack)是限制线性表中元素的插⼊和删除只能在线性表的同⼀端进⾏的⼀种特殊线性表.允许插⼊和删除的⼀端,为变化的⼀端,称为栈顶(Top),另⼀端为固定的⼀端,称为栈底(Bottom). 根据栈的定义可知,最先放⼊栈中元素在栈底,最后放⼊的元素在栈顶,⽽删除元素刚好相反,

  • 详解C++编程中的主表达式与后缀表达式编写基础

    主表达式 主表达式是更复杂的表达式的构造块.它们是文本.名称以及范围解析运算符 (::) 限定的名称.主表达式可以具有以下任一形式: literal this :: name name ( expression ) literal 是常量主表达式.其类型取决于其规范的形式. this 关键字是指向类对象的指针.它在非静态成员函数中可用,并指向为其调用函数的类的实例. this 关键字只能在类成员函数体的外部使用. this 指针的类型是未特别修改 this 指针的函数中的 type *const

  • 带你了解Java数据结构和算法之前缀,中缀和后缀表达式

    目录 1.人如何解析算术表达式 ①.求值 3+4-5 ②.求值 3+4*5 2.计算机如何解析算术表达式 3.后缀表达式 ①.如何将中缀表达式转换为后缀表达式? 一.先自定义一个栈 二.前缀表达式转换为后缀表达式 三.测试 四.结果 五.分析 ②.计算机如何实现后缀表达式的运算? 4.前缀表达式 ①.如何将中缀表达式转换为前缀表达式? ②.计算机如何实现前缀表达式的运算? 总结 1.人如何解析算术表达式 如何解析算术表达式?或者换种说法,遇到某个算术表达式,我们是如何计算的: ①.求值 3+4-

随机推荐