首页 > 其他分享 >习题3.11 表达式转换

习题3.11 表达式转换

时间:2024-07-18 21:01:19浏览次数:20  
标签:return int 3.11 char expr 习题 ElementType Stack 表达式

算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法,即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。

输入格式:

输入在一行中给出不含空格的中缀表达式,可包含+-*/以及左右括号(),表达式不超过20个字符。

输出格式:

在一行中输出转换后的后缀表达式,要求不同对象(运算数、运算符号)之间以空格分隔,但结尾不得有多余空格。

输入样例:

2+3*(7-4)+8/4

输出样例:

2 3 7 4 - * + 8 4 / +
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>

#define MAXL 21
typedef enum{
	false,true
} bool;
typedef char ElementType;

//堆栈定义 
typedef int Position;
typedef struct SNode *PtrToSNode;
struct SNode{
	ElementType *Data;
	Position Top;
	int MaxSize;
}; 
typedef PtrToSNode Stack;
 
Stack createStack(int MaxSize);
bool isEmpty(Stack s);
void push(Stack s,ElementType X);
ElementType pop(Stack s);
ElementType peek(Stack s);

typedef enum{
	lpr,rpr,plus,minus,times,divide,eos,operand
} Precedence;//运算符的优先级类型
bool isSign(char *expr,int i);
char getOp(char *expr,int *i,char *postfix,int *j);
Precedence getToken(char op);
void toPostfix(char *expr);

int main()
{
	char str[MAXL];
	
	scanf("%s",str);
	toPostfix(str);
	return 0;
}

void toPostfix(char *expr)
{
	int i,j,l;
	char postfix[2*MAXL],op;
	Stack s;
	Precedence token;
	
	j=0;
	s=createStack(MAXL);
	l=strlen(expr);
	//j=0;//j指向postfix[]中当前要写入的位置
	for(i=0;i<l;i++){
		op=getOp(expr,&i,postfix,&j);
		token=getToken(op);
		if(token==operand)
			continue;//不处理数字
		switch(token){
			case lpr : push(s,'(');break;//左符号入栈 
			case rpr ://括号内中缀表达式扫描完毕
				//把左括号前的所有运算符写入postfix[] 
				while(peek(s)!='('){
					postfix[j++]=pop(s);
					postfix[j++]=' ';
				}
				pop(s);//删除左括号
				break;
			default ://其他运算符 
				while(!isEmpty(s) && peek(s)!='(' &&  token<=getToken(peek(s))){
					postfix[j++]=pop(s);
					postfix[j++]=' ';
				}
				push(s,op);
				break; 
		} 
	} 
	
	while(!isEmpty(s)){
		postfix[j++]=pop(s);
		postfix[j++]=' ';
	} 
	postfix[j-1]='\0';	
	printf("%s\n",postfix);
}
 //堆栈实现
 Stack createStack(int MaxSize)
 {
 	Stack s=(Stack)malloc(sizeof(struct SNode));
 	s->Data=(ElementType *)malloc(MaxSize*sizeof(ElementType));
 	s->Top=-1;
 	s->MaxSize=MaxSize;
 	return s;
 } 
 bool isEmpty(Stack s)
 {
 	return (s->Top==-1);
 }
 void push(Stack s,ElementType x)
 {
 	//简版入栈,不担心栈满的情况
	 s->Data[++(s->Top)]=x; 
 }
 ElementType pop(Stack s)
 {
 	//简版出栈,不担心栈空
	return (s->Data[(s->Top)--]);
 }
 ElementType peek(Stack s)
 {
 	return s->Data[s->Top];
 } 
 //判断出现'-'为负数,不是运算符减号 
 bool isSign(char *expr,int i)
 {
 	if(!i || ((!isdigit(expr[i-1]) && (expr[i-1]!=')'))))
 		return true;
 	else
 		return false;
 }
char getOp(char *expr,int *i,char *postfix,int *j)
{
 	//如果是数字则直接写入postfix[]并返回'0'
	//如果是运算符则返回字符
	if(isdigit(expr[(*i)]))	{
		while(isdigit(expr[(*i)]) || (expr[(*i)]=='.'))
			postfix[(*j)++]=expr[(*i)++];
		postfix[(*j)++]=' ';
		(*i)--;
		return '0';
	}
	switch(expr[(*i)]){
		case '+':
			if(isSign(expr,(*i))){//如果是正号
				(*i)++;
				return getOp(expr,i,postfix,j) ;
			}else
				return '+';
		case '-':
			if(isSign(expr,(*i))){//如果是负号
				postfix[(*j)++]='-' ;
				(*i)++;
				return getOp(expr,i,postfix,j) ;
			}else
				return '-';
		default:
			return expr[(*i)];
	}
} 
 
Precedence getToken(char op)
{
	//返回运算符优先级
	switch(op){
		case '(':return lpr;
		case ')':return rpr;
		case '+':return plus;
		case '-':return minus;
		case '*':return times;
		case '/':return divide;
		case '\0':return eos;
		default : return operand;
	} 
}

 

标签:return,int,3.11,char,expr,习题,ElementType,Stack,表达式
From: https://blog.csdn.net/qq_33811080/article/details/140472460

相关文章

  • python—正则表达式
    文章目录导入re模块常用的元字符re模块match方法分组贪婪匹配编译Python中的正则表达式是一种强大的文本处理工具,它使用一种特殊的语法来描述字符串的模式。Python通过re模块提供了对正则表达式的支持。使用正则表达式,你可以进行复杂的文本搜索、替换和验证等操作。......
  • Java版本jdk8的特性Lambda表达式详解
    面向对象编程思想和函数式编程思想的区别面向对象编程:重点是对象,强调的是对象的状态和行为。面向对象编程使用类和实例来封装数据和行为,这可以让代码更加模块化和易于维护。函数式编程:重点是函数,强调的是函数的输入和输出,而不是对象的状态。函数式编程通常使用纯函数,即没......
  • 拓扑排序 + 习题
    P4017最大食物链计数 题目链接:https://www.luogu.com.cn/problem/P4017题意:给你一个食物网,求出这个最大食物链的数量最大食物链定义为左端不会捕食其他捕食者,最右端不会被捕食.解释看例子第1行nm表示生物种类n和吃和被吃的关系m接下来m行AB表示A被B吃.........
  • 10 分钟快速搞懂 Lambda 表达式
    Lambda简介Lambda表达式是Java8引入的一个重要特性,相当于一个语法糖。语法糖(Syntacticsugar)是指在编程语言中引入的一种语法,它可以使代码更易读、更简洁,但并没有引入新的功能或改变语言的底层机制。语法糖并不会改变语言的语义,只是提供了一种更方便的编写方式。Lambda表达式......
  • C/C++ 逻辑表达式的注意事项
    在C/C++中,逻辑表达式是用于控制程序流程的重要工具,尤其是在条件语句(如if、while、for等)中。正确使用逻辑表达式对于编写高效、易于理解的代码至关重要。以下是一些使用C/C++逻辑表达式时的注意事项:运算符优先级:逻辑运算符(&&、||、!)具有不同的优先级。!(逻辑非)具有较高的优......
  • 【总结】逻辑运算在Z3中运用+CTF习题
    国际赛IrisCTF在前几天举办,遇到了一道有意思的题目,特来总结。题目附件如下:......
  • 练习题三(7.17)
    任务1、新增账号zhangsanlisiwangwuzhaoliuaaabbbcccddd [root@2~]#useraddzhangsan [root@2~]#useraddlisi [root@2~]#useraddwangwu [root@2~]#useraddzhaoliu [root@2~]#useraddaaa [root@2~]#useraddbbb [root@2~]#useraddccc......
  • C语言运算符与表达式
    1.变量赋初值1.定义时直接赋值    例如:inti=10;变量i初始化。2.先定义,后赋值    例如:inti;i=10;给变量i赋初值。2.C语言算术运算符和算术表达式1.C语言运算符有以下几类算术运算符:包括加(+)、减(-)、乘(*)、除(/)、取余(%)。关系运算符:用于比较两......
  • ES6——Set集合和Map集合练习题
    根据前一篇文章,让ai给我们出下面的练习题:Set练习题创建一个Set并添加数字1到10,然后将其转换为数组并打印。编写一个函数,接收一个数组作为参数,返回一个新的数组,新数组只包含原数组中唯一的元素(去重)。创建一个Set,添加多个元素,然后使用delete方法移除特定元素,打印剩......
  • Android经典面试题之Kotlin中Lambda表达式和匿名函数的区别
    本文首发于公众号“AntDream”,欢迎微信搜索“AntDream”或扫描文章底部二维码关注,和我一起每天进步一点点在Kotlin中,匿名函数和lambda表达式都是用于表示函数类型的匿名函数(即没有名字的函数)。虽然它们在某些情况下可以互换使用,但是它们在语法和使用场景上存在一些细微的......