• 简单表达式的计算（两种方法）

    数据结构中对于栈的运用，最主要的一个例子就是简单表达式的计算了，当你独自将这个程序写出来的时候，这说明你对于栈的运用已经炉火纯青了，下面我将对这个问题做出详细的解答，让我们一起来看看吧

    目录

    问题描述 

    方法一

    1.1 后缀式的转换

    1.2 计算后缀式

    1.3 完整代码

    方法二

    1.1 计算函数 

    1.2 主函数

    1.3 完整代码

    运行结果

    附：系列文章

    问题描述 

     【问题描述】

    设计一个程序，实现简单整数的四则运算（运算对象不小于0），包括加减乘除和小括号。

    【输入形式】

    每行输入一个运算表达式（假设表达式均为正确的表达式），以#作为表达式结束。（表达式长度不超过80）

    【输出形式】

    输出表达式的后缀式

    输出运算结果

    【样例输入】

    23-(2-4)*2+36/(20-14)#

    (100-23)/6+2*(13-9)-40#

    ((100-20)*2)-35#

    120+30+50#

    【样例输出】

    23 2 4 - 2 * - 36 20 14 - / +

    33

    100 23 - 6 / 2 13 9 - * + 40 -

    -20

    100 20 - 2 * 35 -

    125

    120 30 + 50 +

    200

    方法一

    在方法一中呢我们定义两个主要函数，再在主函数中使用两个函数，最终求出表达式的值

    一个函数用来求出原式子的后缀式

    另一个函数用来进行后缀式的计算

    1.1 后缀式的转换

      后缀式的转换是个老生常谈的问题了，对于这个问题一定不能忘了要先设置运算符的优先级

    1. int f(char s){     //我们需要先设置运算符的优先级
    2. 	if(s=='#') return -1;
    3. 	else if(s=='('||s==')') return 0;
    4. 	else if(s=='+'||s=='-') return 1;
    5. 	else if(s=='*'||s=='/') return 2;
    6. }
    7. int Change(char *s1,char *s2){    
    8. 	int i=0,e;
    9. 	PStack S;         
    10. 	S=Init_Stack();
    11. 	Push_Stack(S,'#');      //初始化栈，置栈底为#
    12. 	while(*s1!='#'){   //因为输入#结束，所以最后一个输入的字符是#,当遇到#终止循环
    13. 		if(*s1>='0'&&*s1<='9'){    //遇到非运算符的时候
    14. 			while(*s1>='0'&&*s1<='9'){   //当有连续的非运算符，我们需要把他们放到一起
    15. 				s2[i++]=*s1;
    16. 				s1++;
    17. 			}
    18. 			s2[i++]=' ';    //用空格将
    19.  
    20.  
    21.  
    22. 不同元素隔开，方便后缀式的计算
    23. 			s1--;    //这里的s1--千万不能少！！
    24. 		}else{              //当遇到运算符时
    25. 			Get_Stack(S,&e);     //获取栈顶元素
    26. 			if((f(*s1)>f(e)&&*s1!=')')||*s1=='('){   //如果优先级大于栈顶元素且不是")"
    27. 				Push_Stack(S,*s1);            //或者遇到了"("，直接入栈
    28. 			}else if(*s1==')'){       //如果读取的字符是")"，先出栈，再判断
    29. 				Pop_Stack(S,&e);       
    30. 				while(e!='('){        //遇到非"("的运算符放入后缀式
    31. 					s2[i++]=e;        //遇到"("出栈后不用放到后缀式
    32. 					s2[i++]=' ';
    33. 					Pop_Stack(S,&e);
    34. 				}
    35. 			}else{    //当运算符优先级小于栈顶元素时，出栈放入后缀式直到大于栈顶元素
    36. 				while(f(*s1)<=f(e)){    
    37. 					Pop_Stack(S,&e);
    38. 					s2[i++]=e;
    39. 					s2[i++]=' ';
    40. 					Get_Stack(S,&e);
    41. 				}
    42. 				Push_Stack(S,*s1);    //入栈
    43. 			}
    44. 		}
    45. 		s1++;
    46. 	}
    47. 	while(!Empty_Stack(S)){    //将栈中剩余运算符都放入后缀式
    48. 		Pop_Stack(S,&e);
    49. 		s2[i++]=e;
    50. 	}
    51. 	int k=0;
    52. 	while(1){
    53. 		if(s2[k]=='#') break;
    54. 		printf("%c",s2[k++]);    //打印后缀式
    55. 	}
    56. 	printf("\n");
    57. 	return 1;
    58. }

    1.2 计算后缀式

    计算后缀式的方法是遍历后缀式，每遇到数字字符入栈，遇到运算符时从栈中取两个元素，进行计算，将计算结果放入栈中，用于下一次计算

    1. int Match(char *s){
    2. 	int a,b,x;
    3. 	PStack S;
    4. 	S=Init_Stack();    //初始化一个栈
    5. 	while(*s!='\0'){    //循环
    6. 		if(*s>='0'&&*s<='9'){   //当遇到数字字符时
    7. 			x=0;
    8. 			while(*s>='0'&&*s<='9'){   //使用此方法将字符串转换成整型变量，用于计算
    9. 				x=*s-'0'+x*10;
    10. 				s++;
    11. 			}
    12. 			Push_Stack(S,x);    //入栈
    13. 		}else if(*s!=' '){     //当遇到非空格且不是数字字符时
    14. 			Pop_Stack(S,&a);   //出栈一个数字
    15. 			Pop_Stack(S,&b);   //再出栈一个数字
    16. 			switch(*s){       //进行运算，将运算结果放入栈中
    17. 				case '+':x=a+b;break;
    18. 				case '-':x=b-a;break;
    19. 				case '*':x=a*b;break;
    20. 				case '/':x=b/a;break;
    21. 			}
    22. 			Push_Stack(S,x);  
    23. 		}
    24. 		s++;
    25. 	}
    26. 	Pop_Stack(S,&x);  //最后出栈，打印最后一个元素即是表达式的解
    27. 	printf("%d",x);
    28. 	return 1;
    29. }

    1.3 完整代码

    1. #include
    2. #include
    3. typedef struct Stack{
    4. 	int data;
    5. 	struct Stack * next;
    6. }Stack,*PStack;
    7. PStack Init_Stack(){
    8. 	PStack S=(PStack)malloc(sizeof(Stack));
    9. 	S->next=NULL;
    10. 	return S;
    11. }
    12. int Empty_Stack(PStack S){
    13. 	if(!S->next) return 1;
    14. 	else return 0;
    15. }
    16. int Push_Stack(PStack S,int e){
    17. 	PStack P=(PStack)malloc(sizeof(Stack));
    18. 	P->data=e;
    19. 	P->next=NULL;
    20. 	P->next=S->next;
    21. 	S->next=P;
    22. 	return 1;
    23. }
    24. int Pop_Stack(PStack S,int *e){
    25. 	if(!S->next) return 0;
    26. 	*e=S->next->data;
    27. 	S->next=S->next->next;
    28. 	return 1;
    29. }
    30. int Get_Stack(PStack S,int *e){
    31. 	if(!S->next) return 0;
    32. 	*e=S->next->data;
    33. 	return 1;
    34. }
    35. int f(char s){
    36. 	if(s=='#') return -1;
    37. 	else if(s=='('||s==')') return 0;
    38. 	else if(s=='+'||s=='-') return 1;
    39. 	else if(s=='*'||s=='/') return 2;
    40. }
    41. int Change(char *s1,char *s2){
    42. 	int i=0,e;
    43. 	PStack S;
    44. 	S=Init_Stack();
    45. 	Push_Stack(S,'#');
    46. 	while(*s1!='#'){
    47. 		if(*s1>='0'&&*s1<='9'){
    48. 			while(*s1>='0'&&*s1<='9'){
    49. 				s2[i++]=*s1;
    50. 				s1++;
    51. 			}
    52. 			s2[i++]=' ';
    53. 			s1--;
    54. 		}else{
    55. 			Get_Stack(S,&e);
    56. 			if((f(*s1)>f(e)&&*s1!=')')||*s1=='('){
    57. 				Push_Stack(S,*s1);
    58. 			}else if(*s1==')'){
    59. 				Pop_Stack(S,&e);
    60. 				while(e!='('){
    61. 					s2[i++]=e;
    62. 					s2[i++]=' ';
    63. 					Pop_Stack(S,&e);
    64. 				}
    65. 			}else{
    66. 				while(f(*s1)<=f(e)){
    67. 					Pop_Stack(S,&e);
    68. 					s2[i++]=e;
    69. 					s2[i++]=' ';
    70. 					Get_Stack(S,&e);
    71. 				}
    72. 				Push_Stack(S,*s1);
    73. 			}
    74. 		}
    75. 		s1++;
    76. 	}
    77. 	while(!Empty_Stack(S)){
    78. 		Pop_Stack(S,&e);
    79. 		s2[i++]=e;
    80. 	}
    81. 	int k=0;
    82. 	while(1){
    83. 		if(s2[k]=='#') break;
    84. 		printf("%c",s2[k++]);
    85. 	}
    86. 	printf("\n");
    87. 	return 1;
    88. }
    89. int Match(char *s){
    90. 	int a,b,x;
    91. 	PStack S;
    92. 	S=Init_Stack();
    93. 	while(*s!='\0'){
    94. 		if(*s>='0'&&*s<='9'){
    95. 			x=0;
    96. 			while(*s>='0'&&*s<='9'){
    97. 				x=*s-'0'+x*10;
    98. 				s++;
    99. 			}
    100. 			Push_Stack(S,x);
    101. 		}else if(*s!=' '){
    102. 			Pop_Stack(S,&a);
    103. 			Pop_Stack(S,&b);
    104. 			switch(*s){
    105. 				case '+':x=a+b;break;
    106. 				case '-':x=b-a;break;
    107. 				case '*':x=a*b;break;
    108. 				case '/':x=b/a;break;
    109. 			}
    110. 			Push_Stack(S,x);
    111. 		}
    112. 		s++;
    113. 	}
    114. 	Pop_Stack(S,&x);
    115. 	printf("%d",x);
    116. 	return 1;
    117. }
    118. int main(){
    119.     char s1[100],s2[100];
    120.     scanf("%s",s1);
    121.     Change(s1,s2);
    122.     Match(s2);
    123.     return 0;
    124. }

    方法二

    在方法二中我们只定义了一个计算函数，然后在主函数中边转换后缀式边进行计算（这样大大提高了计算效率）

    1.1 计算函数 

    我们设计一个计算函数，用于后缀式的计算

    1. int match(SqStack *s,char s2)   //函数需要两个参量
    2. {                              //一个是栈，另一个是字符
    3. 	int a,b;          
    4. 	ElemType e;
    5. 	switch(s2)        //定义每一种字符的运算规则
    6. 	{
    7. 		case '+':            
    8. 			GetTop(s,&b);      
    9. 			Pop(s,&e);
    10. 			GetTop(s,&a);
    11. 			Pop(s,&e);
    12. 			Push(s,a+b);
    13. 			break;
    14. 		case '-':
    15. 			GetTop(s,&b);
    16. 			Pop(s,&e);
    17. 			GetTop(s,&a);
    18. 			Pop(s,&e);
    19. 			Push(s,a-b);
    20. 			break;
    21. 		case '*':
    22. 			GetTop(s,&b);
    23. 			Pop(s,&e);
    24. 			GetTop(s,&a);
    25. 			Pop(s,&e);
    26. 			Push(s,a*b);
    27. 			break;
    28. 		case '/':
    29. 			GetTop(s,&b);
    30. 			Pop(s,&e);
    31. 			GetTop(s,&a);
    32. 			Pop(s,&e);
    33. 			Push(s,a/b);
    34. 			break;
    35. 		case '#':break;    
    36. 	}
    37. }

    1.2 主函数

    在主函数中，我们边进行后缀式转换，边进行表达式的计算，大大节省了程序运行的时间

    1. int  main()
    2. {
    3.  
    4. 	char s[100];
    5. 	while(gets(s))
    6. 	{
    7.         SqStack s1,s2;
    8.         InitStack(&s1);   //第一个栈用于转换后缀式
    9.         InitStack(&s2);   //第二个栈用于计算后缀式
    10.         Push(&s1,'#');
    11.         int i;
    12.         for(i=0;i
    13. 		{
    14.             if(s[i]==')')
    15. 			{
    16.                 ElemType e;
    17.                 while(GetTop(&s1,&e)&&e!='(')
    18. 				{
    19.                     printf("%c ",e);      //遇到字符进行运算
    20.                     match(&s2,e);
    21.                     Pop(&s1,&e);     //取出这个字符
    22.                 }
    23.                 Pop(&s1,&e);    //遇到"("时取出就好
    24.             }
    25.             else if(s[i]>='0'&&s[i]<='9')  //遇到数字时
    26. 			{
    27.                 int x=0;
    28.                 while(s[i]>='0'&&s[i]<='9')   //先将数字转换为整型
    29. 				{
    30.                     x=x*10+(s[i]-'0');
    31.                     i++;
    32.                 }
    33.                 Push(&s2,x);    //将整型变量放入栈中，用于运算
    34.                 printf("%d ",x);
    35.                 i--;
    36.             }
    37.             else
    38. 			{
    39.                 ElemType e;
    40.                 if(s[i]!='(') //当你遇到的字符不是"("
    41. 				{
    42.                     while(GetTop(&s1,&e)&&f(s[i])<=f(e))  //且运算符优先级小于栈顶元素
    43. 					{
    44.                         if(e!='#')printf("%c ",e);    
    45.                         match(&s2,e);      //执行运算
    46.                         Pop(&s1,&e);      //取出栈顶元素，继续下一次判断
    47.                     }
    48.                 }
    49.                 Push(&s1,s[i]);   //直到优先级大于栈顶元素，入栈
    50.             }
    51.         }
    52.         int m; 
    53.         GetTop(&s2,&m);   //栈中最后只剩栈底元素"#"和最后一个值，最后一个值就是表达式结果
    54.         printf("\n%d",m);
    55. 	}
    56. 	return  ERROR;
    57. }

    1.3 完整代码

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #define  ERROR  0
    6. #define  OK  1
    7. typedef  int  ElemType;
    8. typedef  struct  StackNode
    9. {
    10. 	ElemType data;
    11. 	struct StackNode *next;
    12. }StackNode,*SqStack;
    13. int InitStack(SqStack *s)
    14. {
    15. 	(*s)=NULL;
    16. 	return OK;
    17. }
    18. int EmptyStack(SqStack *s)
    19. {
    20. 	if(*s==NULL) return OK;
    21. 	else return ERROR;
    22. }
    23. int Push(SqStack *s,ElemType e)
    24. {
    25. 	SqStack p;
    26. 	p=(SqStack)malloc(sizeof(StackNode));
    27. 	p->data=e;
    28. 	p->next=*s;
    29. 	*s=p;
    30. 	return OK;
    31. }
    32. int Pop(SqStack *s,ElemType *e)
    33. {
    34. 	if(*s==NULL) 
    35. 	     return ERROR;
    36. 	else
    37. 	{
    38. 		SqStack p;
    39. 		p=*s;
    40. 		*e=p->data;
    41. 		*s=(*s)->next;
    42. 		free(p);
    43. 		return OK;
    44. 	}
    45. }
    46. int GetTop(SqStack *s,ElemType *e)
    47. {
    48. 	if(*s==NULL) 
    49. 	    return ERROR;
    50. 	else
    51. 	{
    52. 		*e=(*s)->data;
    53. 		return OK;
    54. 	}
    55. }
    56. int f(char s2)
    57. {
    58. 	if(s2=='#') return -1;
    59. 	else if(s2=='(') return 0;
    60. 	else if(s2=='+'||s2=='-') return 1;
    61. 	else if(s2=='*'||s2=='/') return 2;
    62. }
    63. int match(SqStack *s,char s2)
    64. {
    65. 	int a,b;
    66. 	ElemType e;
    67. 	switch(s2)
    68. 	{
    69. 		case '+':
    70. 			GetTop(s,&b);
    71. 			Pop(s,&e);
    72. 			GetTop(s,&a);
    73. 			Pop(s,&e);
    74. 			Push(s,a+b);
    75. 			break;
    76. 		case '-':
    77. 			GetTop(s,&b);
    78. 			Pop(s,&e);
    79. 			GetTop(s,&a);
    80. 			Pop(s,&e);
    81. 			Push(s,a-b);
    82. 			break;
    83. 		case '*':
    84. 			GetTop(s,&b);
    85. 			Pop(s,&e);
    86. 			GetTop(s,&a);
    87. 			Pop(s,&e);
    88. 			Push(s,a*b);
    89. 			break;
    90. 		case '/':
    91. 			GetTop(s,&b);
    92. 			Pop(s,&e);
    93. 			GetTop(s,&a);
    94. 			Pop(s,&e);
    95. 			Push(s,a/b);
    96. 			break;
    97. 		case '#':break;
    98. 	}
    99. }
    100. int  main()
    101. {
    102.  
    103. 	char s[100];
    104. 	while(gets(s))
    105. 	{
    106.         SqStack s1,s2;
    107.         InitStack(&s1);
    108.         InitStack(&s2);
    109.         Push(&s1,'#');
    110.         int i;
    111.         for(i=0;i
    112. 		{
    113.             if(s[i]==')')
    114. 			{
    115.                 ElemType e;
    116.                 while(GetTop(&s1,&e)&&e!='(')
    117. 				{
    118.                     printf("%c ",e);
    119.                     match(&s2,e);
    120.                     Pop(&s1,&e);
    121.                 }
    122.                 Pop(&s1,&e);
    123.             }
    124.             else if(s[i]>='0'&&s[i]<='9')
    125. 			{
    126.                 int x=0;
    127.                 while(s[i]>='0'&&s[i]<='9')
    128. 				{
    129.                     x=x*10+(s[i]-'0');
    130.                     i++;
    131.                 }
    132.                 Push(&s2,x);
    133.                 printf("%d ",x);
    134.                 i--;
    135.             }
    136.             else
    137. 			{
    138.                 ElemType e;
    139.                 if(s[i]!='(')
    140. 				{
    141.                     while(GetTop(&s1,&e)&&f(s[i])<=f(e))
    142. 					{
    143.                         if(e!='#')printf("%c ",e);
    144.                         match(&s2,e);
    145.                         Pop(&s1,&e);
    146.                     }
    147.                 }
    148.                 Push(&s1,s[i]);
    149.             }
    150.         }
    151.         int m;
    152.         GetTop(&s2,&m);
    153.         printf("\n%d",m);
    154. 	}
    155. 	return  ERROR;
    156. }

    运行结果

    附：系列文章

    序号文章目录直达链接
    1顺序表的十个基本操作（全）https://want595.blog.csdn.net/article/details/127139051
    2单链表的十三个基本操作（全）https://want595.blog.csdn.net/article/details/127139598
    3四种创建单链表的方法https://want595.blog.csdn.net/article/details/127017405
    4删除重复元素（顺序表、单链表）https://want595.blog.csdn.net/article/details/127023468
    5两个有序表的合并（三种方法）https://want595.blog.csdn.net/article/details/127104602
    6一元多项式相加问题（两种方法）https://want595.blog.csdn.net/article/details/127131351
    7约瑟夫环问题（三种方法）https://want595.blog.csdn.net/article/details/127019472
    8顺序栈与链栈https://want595.blog.csdn.net/article/details/127035609
    9顺序循环队列与链队列https://want595.blog.csdn.net/article/details/127040115
    10后缀表达式的转换（栈的运用）https://want595.blog.csdn.net/article/details/127088466
    11简单表达式的计算（两种方法）https://want595.blog.csdn.net/article/details/127121720
    12next数组（详细求法）https://want595.blog.csdn.net/article/details/127217629
    13BF算法（具体应用）https://want595.blog.csdn.net/article/details/127138894
    14串的模式匹配相关问题（BF算法、KMP算法）https://want595.blog.csdn.net/article/details/127182721
    15二叉树的遍历（七种方法）https://want595.blog.csdn.net/article/details/127472445

     

  • 相关阅读:
    微服务架构的外部 API 集成模式
    JAVA毕业设计二手车商城计算机源码+lw文档+系统+调试部署+数据库
    算法--差分
    java导出Mysql表信息生成Word文档
    前端vue element axios混编团队发送数据到后端，后端接受使用的是$_POST
    Android 导入ncnn-android-yolov8-seg : 实现人体识别和人像分割
    华为路由器升级系统文件
    错误模块路径: ...\v4.0.30319\clr.dll，v4.0.30319 .NET 运行时中出现内部错误，进程终止，退出代码为 80131506。
    java毕业设计研究生实验室综合管理系统Mybatis+系统+数据库+调试部署
    根文件系统介绍
  • 原文地址：https://blog.csdn.net/m0_68111267/article/details/127121720