50字范文 > 中缀表达式求值后缀表达式求值中缀转后缀前缀

中缀表达式求值后缀表达式求值中缀转后缀前缀

时间：2021-11-27 19:05:26

1.中缀表达式求值

两个栈：OPND（double类数）,OPTR（操作符）。
需要比较栈里和栈外ch的操作符优先级。
运用到atof()函数（stdlib.h），将*char 转换为 double。

#include<iostream>#include<iomanip>#include<string.h>#include<stdlib.h>using namespace std;#define MAXSIZE 1000typedef struct{double *base;double *top;int stacksize;}SqStack_d;void Init(SqStack_d &S){S.base = new double[MAXSIZE];S.top = S.base;S.stacksize = MAXSIZE;}void Push(SqStack_d &S, double e){if(S.top - S.base != S.stacksize){*S.top = e;S.top++;}}void Pop(SqStack_d &S, double &e){if(S.top !=S.base){S.top--;e = *S.top;}}double GetTop(SqStack_d S){if(S.base !=S.top){return *(S.top-1);}}typedef struct{char *base;char *top;int stacksize;}SqStack_c;void Init(SqStack_c &S){S.base = new char[MAXSIZE];S.top = S.base;S.stacksize = MAXSIZE;}void Push(SqStack_c &S, char e){if(S.top - S.base != S.stacksize){*S.top = e;S.top++;}}void Pop(SqStack_c &S, char &e){if(S.top !=S.base){S.top--;e = *S.top;}}char GetTop(SqStack_c S){if(S.base !=S.top){return *(S.top-1);}}bool In( char ch){if(ch>='0'&&ch<='9'){return true;}else return false;}char Com(char c1,char c2)//c1:in c2:out or ch{if((c1=='('&&c2==')')||(c1=='='&&c2=='='))return '=';else if(((c1=='+'||c1=='-')&&(c2=='+'||c2=='-'||c2==')'||c2=='='))||((c1=='*'||c1=='/'||c1==')')&&(c2=='+'||c2=='-'||c2=='*'||c2=='/'||c2==')'||c2=='=')))return '>';else return '<';}double Operate(double a,char x,double b)// ASCALL{switch(x){case '+':return (a+b);break;case '-':return (a-b);break;case '*':return (a*b);break;case '/':return (a/b);break;}}double Expression(char s[]){// 5*(7-3)#SqStack_d OPND;SqStack_c OPTR;Init(OPND);Init(OPTR);Push(OPTR,'=');//# 要入栈char ch;int k=0;ch = s[k];double item;while(ch != '=' || GetTop(OPTR)!='=')// GetTop(OPTR)!='=' 防止ch== '='，OPTR中还有操作符{if(In(ch))// ch = 4 .5{char sd[MAXSIZE];memset(sd,0,sizeof(sd));int i=0;while((ch>='0'&&ch<='9')||(ch=='.')){sd[i] = ch;k++;ch = s[k];i++;}item = atof(sd);Push(OPND,item);}else{switch(Com(GetTop(OPTR),ch)){case '<':{Push(OPTR,ch);k++;ch = s[k];break;}case '>':{double a,b;char op;Pop(OPTR,op);Pop(OPND,a);Pop(OPND,b);Push(OPND,Operate(b,op,a));break;// can't cin>>ch}case '=':{char x;Pop(OPTR,x);k++;ch = s[k];break;}}}}return GetTop(OPND);}int main(){char s[MAXSIZE];while(1){cin>>s;if(s[0] == '='){break;}cout<<setiosflags(ios::fixed)<<setprecision(2)<<Expression(s)<<endl;}return 0;}

还待优化：两个栈，如何用一个共享栈，共用体结构；是否可以只用一个char栈

###2. 后缀表达式求值 ###

后缀表达式（从左向右扫描），表达式中的操作符已包含优先级，且无括号操作符，无需再比较优先级。
比中缀表达式简单
一个栈：OPND（double操作数）

###3.中缀转后缀###

一个栈：OPTR（操作符）
从左向右扫描中缀表达式：
遇数，输出；
遇符：
栈里<栈外，栈外进栈，输入下一个字符；
栈里==栈外，pop,输入下一个字符；
栈里>栈外,栈里pop，并输出。

#include<iostream>#include<string>using namespace std;#define MAXSIZE 1000typedef struct{char *base;char *top;int stacksize;}SqStack_c;void Init(SqStack_c &S){S.base = new char[MAXSIZE];S.top = S.base;S.stacksize = MAXSIZE;}void Push(SqStack_c &S, char e){if(S.top - S.base != S.stacksize){*S.top++ = e;}}void Pop(SqStack_c &S, char &e){if(S.top !=S.base){S.top--;e = *S.top;}}char GetTop(SqStack_c S){if(S.base !=S.top){return *(S.top-1);}}char Com(char c1,char c2){if(((c1=='+'||c1=='-')&&(c2=='+'||c2=='-'||c2==')'||c2=='='))||((c1=='*'||c1=='/'||c1==')')&&(c2=='+'||c2=='-'||c2=='*'||c2=='/'||c2==')'||c2=='='))){return '>';}else if((c1=='='&&c2=='=')||(c1=='('&&c2==')')){return '=';}else{return '<';}}void Mid_to_Pos(string s){SqStack_c OPTR;Init(OPTR);int k=0;char ch = s[0];Push(OPTR,'=');while(ch!='=' || GetTop(OPTR)!= '='){if(ch>='0'&&ch<='9'){cout<<ch;ch = s[++k];}else{switch(Com(GetTop(OPTR),ch)){case '>':char e;Pop(OPTR,e);cout<<e;break;case '<':Push(OPTR,ch);ch = s[++k];break;case '=':char x;Pop(OPTR,x);ch = s[++k];break;}}}cout<<endl;}int main(){while(1){string s;cin>>s;if(s =="="){break;}Mid_to_Pos(s);}}

###4.关于前缀###