中缀表达式转换为后缀表达式是堆栈的一个典型例题 .
→ 从头到尾读取中缀表达式的每个对象,对不同的对象按照不同的情况处理.
①运算数:直接输出;
②左括号:压入堆栈;
③右括号:将栈顶的元算服弹出并输出直到遇见左括号(出栈不输出);
④运算符:
若优先级大于栈顶运算符时压栈;
若优先级小于栈顶运算符时,将栈顶运算符弹出并输出;再比较新的栈顶运算符,知道该运算符大于栈顶运算符优先级为止,然后将运算符压栈;
⑤若各对象处理完毕,则把堆栈中保留的运算符一并输出.
堆栈有很多的用途,例如函数的调用,在调用函数的的时候,就将调用函数的上一层储存到 栈里面,,所以当用函数的递归的时候就会占用很多的内存,容易导致崩溃,,,前面说过这个问题的例子.
下面附上实现代码
可能看起来比较困难一点,但是不要着急,先看看混个脸熟
#include<stdio.h> #include<string.h> #include<stack> #include<stdlib.h> using namespace std; char a[1010]; char b[1010]; stack <char> s1; stack <float> s2; int i,j,n,m,t; float x,y,z; int fun(char x) { switch(x) { case '+' : case '-' :return 1; case '*' : case '/' :return 2; case '(' :return 0; default :return -1; } } float js(float x,float y,char z) { switch(z) { case '+':return y+x; case '-':return y-x; case '*':return y*x; default :return y/x; } } int main() { int p; char c[1010]; float d; scanf("%d",&t); s1.push('#'); while(t--) { j=0; scanf("%s",a); m=strlen(a)-1; for(i=0;i<m;i++) { if(a[i]>='0'&&a[i]<='9'||a[i]=='.') { memset(c,0,sizeof(c)); p=0; while(a[i]>='0'&&a[i]<='9'||a[i]=='.') { b[j++]=a[i]; c[p++]=a[i++]; } d=atof(c); s2.push(d); i--; } else if(a[i]=='(') s1.push(a[i]); else if(a[i]==')') { while(s1.top()!='(') { b[j++]=s1.top(); x=s2.top();s2.pop(); y=s2.top();s2.pop(); x=js(x,y,b[j-1]); s2.push(x); s1.pop(); } s1.pop(); } else { while(fun(s1.top())>=fun(a[i])) { b[j++]=s1.top(); x=s2.top();s2.pop(); y=s2.top();s2.pop(); x=js(x,y,b[j-1]); s2.push(x); s1.pop(); } s1.push(a[i]); } } while(s1.top()!='#') { b[j++]=s1.top(); x=s2.top();s2.pop(); y=s2.top();s2.pop(); x=js(x,y,b[j-1]); s2.push(x); s1.pop(); } b[j]='='; b[j+1]=' '; puts(b); printf("%.2f ",s2.top()); s2.pop(); } return 0; }
堆栈的应用:
→函数调用以及递归实现
→深度优先搜索
→回朔算法
→．．．．．