时间:2021-05-20
本文实例为大家分享了C++实现中缀表达式转后缀表达式的具体代码,供大家参考,具体内容如下
题目:现有中缀表达式如:1+(2-3)*4+10/5
请用栈的特性编写一个程序,使得程序输出后缀表达式
分析如下:
STEP1:
1+(2-3)*4+10/5
首先遇到第一个输入是数字1,数字在后缀表达式中都是直接输出,接着是符号“+”,入栈:
STEP2:
1+(2-3)*4+10/5
第三个字符是“(”,依然是符号,入栈,接着是数字2,输出,然后是符号“-”,入栈:
STEP3:
1+(2-3)*4+10/5
接下来是数字3,输出,紧跟着是“)”,此时,我们需要去匹配栈里的“(”,然后再匹配前将栈顶数据依次出栈(这就好比括号里优先执行的道理):
STEP4:
1+(2-3)*4+10/5
紧接着是符号“*”,直接入栈
STEP5:
1+(2-3)*4+10/5
遇到数字4,输出,之后是符号“+”,此时栈顶元素是符号“*”,按照先乘除后加减原理,此时栈顶的乘号优先级比即将入栈的加好要大,所以出栈。
栈中第二个元素是加号,按理来说大家平起平坐,但是按照先来后到的原则,栈里的加号呆得太久了,也要出栈透透气。(同理如果栈里还有其他操作符,也是出栈)
最后把刚刚的那个加号入栈,操作如下图:
STEP6:
1+(2-3)*4+10/5
紧接着数字10,输出,最后是符号“/”,进栈:
STEP7:
1+(2-3)*4+10/5
最后一个数字5,输出,所有的输入处理完毕,但是栈中仍然有数据,所以将栈中符号依次出栈。
总结规则:
从左到右遍历中缀表达式的每个数字和符号,若是数字则直接输出,若是符号,则判断其与栈顶符号的优先级,是右括号或者优先级低于栈顶符号,则栈顶元素依次出栈并输出,直到遇到左括号或栈空才将低优先级的那个符号入栈
代码实现如下:
#include <stdio.h>#include <stdlib.h> #define STACK_INIT_SIZE 20#define STACKINCREMENT 10 typedef char ElemType;typedef struct{ ElemType *base; ElemType *top; int stackSize;}sqStack; InitStack(sqStack *s){ s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType)); if( !s->base ) exit(0); s->top = s->base; s->stackSize = STACK_INIT_SIZE;} Push(sqStack *s, ElemType e){ // 栈满,追加空间,鱼油必须懂! if( s->top - s->base >= s->stackSize ) { s->base = (ElemType *)realloc(s->base, (s->stackSize + STACKINCREMENT) * sizeof(ElemType)); if( !s->base ) exit(0); s->top = s->base + s->stackSize; s->stackSize = s->stackSize + STACKINCREMENT; } *(s->top) = e; // 存放数据 s->top++;} Pop(sqStack *s, ElemType *e){ if( s->top == s->base ) return; *e = *--(s->top); // 将栈顶元素弹出并修改栈顶指针} int StackLen(sqStack s){ return (s.top - s.base);} int main(){ sqStack s; char c, e; InitStack( &s ); printf("请输入中缀表达式,以#作为结束标志:"); scanf("%c", &c); while( c != '#' ) { while( c>='0' && c<='9' ) { printf("%c", c); scanf("%c", &c); if( c<'0' || c>'9' ) { printf(" "); } } if( ')' == c ) { Pop(&s, &e); while( '(' != e ) { printf("%c ", e); Pop(&s, &e); } } else if( '+'==c || '-'==c ) { if( !StackLen(s) ) { Push(&s, c); } else { do { Pop(&s, &e); if( '(' == e ) { Push(&s, e); } else { printf("%c ", e); } }while( StackLen(s) && '('!=e ); Push(&s, c); } } else if( '*'==c || '/'==c || '('==c ) { Push(&s, c); } else if( '#'== c ) { break; } else { printf("\n出错:输入格式错误!\n"); return -1; } scanf("%c", &c); } while( StackLen(s) ) { Pop(&s, &e); printf("%c ", e); } return 0;}以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
本文实例为大家分享了C语言实现中缀表达式转后缀表达式的具体代码,供大家参考,具体内容如下中缀表达式转换为后缀表达式(思路)1.创建栈2.从左向右顺序获取中缀表达
本文实例为大家分享了C++实现中缀表达式转后缀表达式的具体代码,供大家参考,具体内容如下一、思路:和中缀表达式的计算类似,只不过不用计算,把表达式输出即可1.用
在进行一个表达式的计算时,先将表达式分割成数字和字符串然后利用出入栈将分割后的表达式进行中缀转后缀,再将后缀表达式进行计算得到结果(思想在上一篇写过)现在贴下J
本文实例为大家分享了C++中缀表达式转后缀表达式的具体代码,供大家参考,具体内容如下1、初始化两个栈:运算符栈s1和储存中间结果的栈s2;2、从左至右扫描中缀表
C语言数据结构之中缀树转后缀树的实例对于一个中缀表达式a+b*c*(d-e/f)转换成后缀是这样的形式abc*def/-+后缀表达式是相当有用处的,转换成后缀表