专业网站设计发展前景,旅游网站建设与网页设计意义,网站打开是别人的,用ip做网站题目描述 小明在学习了数据结构之后#xff0c;突然想起了以前没有解决的算术表达式转化成后缀式的问题#xff0c;今天他想解决一下。因为有了数据结构的基础小明很快就解出了这个问题#xff0c;但是他突然想到怎么求出算术表达式的前缀式和中缀式呢#xff1f;小明很困惑… 题目描述 小明在学习了数据结构之后突然想起了以前没有解决的算术表达式转化成后缀式的问题今天他想解决一下。 因为有了数据结构的基础小明很快就解出了这个问题但是他突然想到怎么求出算术表达式的前缀式和中缀式呢小明很困惑。聪明的你帮他解决吧。 输入
输入一算术表达式以\#\字符作为结束标志。数据保证无空格,只有一组输入输出
输出该表达式转换所得到的前缀式 中缀式 后缀式。分三行输出顺序是前缀式 中缀式 后缀式。示例输入 a*b(c-d/e)*f# 示例输出 *ab*-c/def
a*bc-d/e*f
ab*cde/-f* 前缀规律 1) 设立操作符栈OPTR结果栈RESULT 2) 从右向左遍历若当前字符是操作数则直接发送给RESULT栈 3) 若当前运算符的优先数高于等于栈顶运算符则进OPTR栈 4) 否则退出栈顶运算符发送给RESULT栈 5) “” 对它之前后的运算符起隔离作用“”可视为自相应右括弧开始的表达式的结束符。(即读到右括号时总是将它压入OPTR栈中,读到左括号时将靠近栈顶的第一个右括号上面的运算符全部依次弹出送至RESULT栈后再丢弃右括号。 后缀规律 1) 设立操作符栈 2) 若当前字符是操作数则直接发送给后缀式 3) 若当前运算符的优先数高于栈顶运算符则进栈 4) 否则退出栈顶运算符发送给后缀式 5) “(” 对它之前后的运算符起隔离作用“)”可视为自相应左括弧开始的表达式的结束符。(即读到左括号时总是将它压入栈中读到右括号时将靠近栈顶的第一个左括号上面的运算符全部依次弹出送至输出队列后再丢弃左括号。 ) #include iostream #include cstdio #include cstdlib #include cstring #include cmath #include algorithm using namespace std; int cmp(char c)//运算符的优先级 { if(c ||c -) return 1 ; if(c *||c /) return 2 ; if(c () return 3 ; if(c )) return 4 ; return 0 ; } void Qianzhui(char a[])//前缀式的获得数组模拟栈 { int top2 -1, top3-1; int l strlen(a); char stack2[100], stack3[100]; for(int i l-2; i 0; i--)//从后往前读入 { if(a[i] aa[i] z)//是英文则进数组stack3 { stack3[top3] a[i]; } else { if(top2 -1||stack2[top2] )|| a[i] ))//进数组stack2的条件 { stack2[top2] a[i]; } else if(a[i] () { while(stack2[top2] ! )) { stack3[top3] stack2[top2--]; } top2--; } else { if(cmp(a[i]) cmp(stack2[top2]))//比较运算优先顺序 { stack3[top3] stack2[top2--]; i; } else { stack2[top2] a[i]; } } } } while(top2 ! -1)//将数组stack2的所有元素挪进stack3 { stack3[top3] stack2[top2--]; } for(int i top3; i 0; i--)//逆序输出数组的所有元素 printf(%c, stack3[i]); printf(\n); } void Zhongzhui(char a[])//中缀式的获得 { for(int i 0; a[i] ! #; i) { if(a[i] !( a[i] ! )) printf(%c, a[i]); } printf(\n); } void Houzhui(char a[])//后缀式的获得 { int top1 0; char stack1[100] ; for(int i 0; a[i] ! #; i) { if(a[i] aa[i] z)//是字母则直接输出 { printf(%c, a[i]) ; } else { if(top1 0)//数组空则直接进数组 { top1 ; stack1[top1] a[i] ; } else if(cmp(a[i]) cmp(stack1[top1]))//优先运算的比较 { if(cmp(a[i]) 4) { while(stack1[top1] ! () { printf(%c, stack1[top1--]); } top1-- ; } else { top1 ; stack1[top1] a[i]; } } else { if(stack1[top1] ! () { printf(%c, stack1[top1]) ; stack1[top1] a[i] ; } else { top1 ; stack1[top1] a[i] ; } } } } while(top1 ! 0)//数组所有元素的输出 { printf(%c, stack1[top1]) ; top1-- ; } printf(\n) ; } int main() { char a[1005]; scanf(%s,a); Qianzhui(a);//前缀式 Zhongzhui(a);//中缀式 Houzhui(a);//后缀式 } #include stdio.h #include stdlib.h #include string.h #define stackmax 10000 #define stacknum 10000 typedef int elemtype; typedef struct { elemtype *base; elemtype *top; int stacksize; } sqstack; int initstack(sqstack s)//栈的初始化 { s.base (elemtype *)malloc(stackmax * sizeof(elemtype)); if(!s.base) exit(0); s.top s.base; s.stacksize stackmax; } char push(sqstack s, char e)//进栈 { if(s.top - s.base s.stacksize) { s.base (elemtype *)realloc(s.base,(s.stacksizestacknum) * sizeof(elemtype)); if(!s.base) exit(0); s.top s.base s.stacksize; s.stacksize stacknum; } *s.tope; } int pop(sqstack s)//出栈 { if(s.tops.base) return 0; s.top--; return 1; } char gettop(sqstack s)//获得栈顶元素 { if(s.top s.base) return 0; char e *(s.top-1); return e; } int stackempty(sqstack s)//判断栈是否为空 { if(s.top s.base) return 1; else return 0; } int cmp(char c)//用于比较优先级 { if (c||c-) return 1; if (c*||c/) return 2; if (c() return 3; if (c)) return 4; } char lasttranslate(sqstack s, char c[])//后缀式的获得 { int nstrlen(c); int i; for(i0; in; i) { if (c[i]ac[i]z) printf(%c, c[i]); else { if(c[i]!#) { if(stackempty(s)) { push(s, c[i]); } else { if(cmp(c[i])cmp(gettop(s))) { if(c[i])) { while(gettop(s)!() { printf(%c, *(s.top-1)); pop(s); } pop(s); } else { push(s, c[i]); } } else { if(gettop(s)() push(s, c[i]); else { printf(%c, gettop(s)); pop(s); push(s,c[i]); } } } } } } } char pretranslate(sqstack s1, sqstack s2, char c[])//前缀式的获得 { int nstrlen(c); int i; for(in-2; i0; i--)//逆序读入 { if (c[i]ac[i]z) push(s1, c[i]); else if(stackempty(s2)) { push(s2, c[i]); } else { if(cmp(c[i])cmp(gettop(s2))) { if(c[i]() { while(gettop(s2)!)) { push(s1, *(s2.top-1)); pop(s2); } pop(s2); } else { push(s2, c[i]); } } else { if(gettop(s2))) push(s2, c[i]); else { push(s1, gettop(s2)); pop(s2); push(s2,c[i]); } } } } } void putstack1(sqstack s)//栈内所有元素的输出 { while(s.top s.base) { printf(%c, *(s.top-1)); s.top--; } } void putstack2(sqstack s) { while(s.top s.base) { printf(%c, *(s.base)); s.base; } } char midtranlate(char c[])//中缀式的获得 { int nstrlen(c), i; for(i0;in;i) { if(c[i]!(c[i]!)c[i]!#) printf(%c, c[i]); } } int main() { char c[110]; sqstack s;//定义栈 sqstack s1, s2; initstack(s);//初始化栈 initstack(s1); initstack(s2); scanf(%s, c); pretranslate(s1, s2, c);//前缀式 putstack2(s2);//前缀式的输出 putstack1(s1); printf(\n); midtranlate(c);//中缀式的输出 printf(\n); lasttranslate(s, c);//后缀式 putstack1(s);//栈可能不为空 return 0; }
