| 表达式求值（最详细分析+代码实现+表达式之间的相互转换） | 您所在的位置：网站首页 › 左括号右括号怎么填 › 表达式求值（最详细分析+代码实现+表达式之间的相互转换） |
表达式求值（最详细分析+代码实现+表达式之间的相互转换）
|
目录 一、概念 二、前缀表达式的逻辑和实现方式 1.定义 2.前缀表达式的计算机求值 3.例子 4.代码实现 三、中缀表达式的逻辑和实现方式 1.定义 2.中缀表达式规则 3.中缀表达式的计算机求值 4.代码实现 四、后缀表达式的逻辑和实现方式（逆波兰表达式求值） 1.定义 2.后缀表达式计算机求值 3.例子 4.代码实现 五、相互转换 1.中缀表达式转化为前缀表达式 ①算法描述 ②例子 2.前缀表达式转化为中缀表达式 3.中缀表达式转化为后缀表达式 ①算法描述 ②例子 ③代码实现 4.后缀表达式转化为中缀表达式 六、总结 1.常用表达式求值分析 ①方法 ②优缺点 2.相互转换分析 3.总结 一、概念 算术表达式是由操作数（运算数）、运算符（操作符）、和界线符（括号）三部分组成，在计算机中进行算术表达式的计算是通过堆栈来实现的。 二、前缀表达式的逻辑和实现方式 1.定义如果是在两个操作数之前，那么这个表达式就是前缀表达式，又称波兰表达式，如：-*+3 5 7 1 2.前缀表达式的计算机求值1.从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时， 2.弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素 op 次顶元素）， 3.并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果 3.例子计算前缀表达式的值：- + 1 × + 2 3 4 5 1)从右至左扫描，将5，4，3，2压入堆栈； 2）遇到+运算符，弹出2和3（2为栈顶元素，3为次顶元素），计算2+3的值，得到5，将5压入栈； 3）遇到×运算符，弹出5和4，计算5×4的值，得到20，将20压入栈； 4）遇到1，将1压入栈； 5）遇到+运算符，弹出1和20，计算1+20的值，得到21，将21压入栈； 6）遇到-运算符，弹出21和5，计算5-21的值，得到-16为最终结果 可以看到，用计算机计算前缀表达式是非常容易的，不像计算后缀表达式需要使用正则匹配 4.代码实现三、中缀表达式的逻辑和实现方式 1.定义 如果是跟在两个操作数之间，那么这个表达式就是中缀表达式,如：(3 + 5) * 7 - 1 2.中缀表达式规则(1) 先计算括号内，后计算括号外； (2) 在无括号或同层括号内，先乘除运算，后加减运算，即乘除运算的优先级高于加减运算的优先级； (3) 同一优先级运算，从左向右依次进行。 3.中缀表达式的计算机求值 设置两个栈，一个数字栈numStack，用于存储表达式中涉及到的数字，operatorStack用于存储表达式中涉及到的运算符逐个字符分析表达式，直到全部字符都已分析完 若当前字符为数字，则判断是否后续字符也为数字，若为数字则进行拼接，直到下一个数字为运算符为止，此时将拼接好的多位数字压入数字栈中。（如果已经是最后一个字符则直接压入栈）若当前字符为算数运算符 如果运算符栈为空则直接压入栈中运算符不为空，则对运算符优先级进行判断 如果当前运算符优先级大于等于栈顶运算符则直接压入栈中如果优先级低于栈顶运算符，则，从数字栈中取出两个数据，将当前栈顶运算符弹出进行运算，将结果压入数字栈中，将当前运算符压入运算符栈中。此时数字与运算符都已经压入栈中，此时运算符栈中均为优先级相同的运算符，需要进行收尾操作，如果运算符栈不为空，则依次从数字栈中弹出两个数据，与当前栈顶的运算符进行运算。将结果压入数字栈中。最后数字栈中的数字就是所要求解的结果 4.代码实现 #include #include #include #include #include #define maximum 100000 typedef struct//数字栈 { float data[maximum]; int top; }number; typedef struct//字符栈 { char data[maximum]; int top; }sign; void InitNumber(number *stack);//初始化数字栈 void GetTopNumber(number stack, float *e);//获取栈顶元素 void PushNumber(number *stack, float e);//进栈 void PopNumber(number *stack, float *e);//出栈 void InitSign(sign *stack); void GetTopSign(sign stack, char *e); void PushSign(sign *stack, char e); void PopSign(sign *stack, char *e); void Calculate(number *stack, char e); number Num; sign sig; char expression[maximum]; int main() { gets(expression); int length; length=strlen(expression); int i; float en,n; char es; InitNumber(&Num); InitSign(&sig); for (i=0;i='0'&&expression[i]='0'&&expression[i+1]0&&sig.data[sig.top-1]!='(')//如果栈不为空切不为左括号，则出栈 { PopSign(&sig,&es); Calculate(&Num,es); } PushSign(&sig,'+'); } break; case '-': if(sig.data[sig.top-1]!='+'&&sig.data[sig.top-1]!='-'&&sig.data[sig.top-1]!='*'&&sig.data[sig.top-1]!='/'&&sig.data[sig.top-1]!='^') PushSign(&sig,'-'); else { while (sig.top>0&&sig.data[sig.top-1]!='(') { PopSign(&sig,&es); Calculate(&Num,es); } PushSign(&sig,'-'); } break; case '*': if(sig.data[sig.top-1]!='*'&&sig.data[sig.top-1]!='/'&&sig.data[sig.top-1]!='^') PushSign(&sig,'*'); else { while (sig.top>0&&sig.data[sig.top-1]!='(') { PopSign(&sig,&es); Calculate(&Num,es); } PushSign(&sig,'*'); } break; case '/': if(sig.data[sig.top-1]!='*'&&sig.data[sig.top-1]!='/'&&sig.data[sig.top-1]!='^') PushSign(&sig,'/'); else { while (sig.top>0&&sig.data[sig.top-1]!='(') { PopSign(&sig,&es); Calculate(&Num,es); } PushSign(&sig,'/'); } break; case '^': if(sig.data[sig.top-1]!='^') PushSign(&sig,'^'); else { while (sig.top>0&&sig.data[sig.top-1]!='(') { PopSign(&sig,&es); Calculate(&Num,es); } PushSign(&sig,'^'); } case '(': PushSign(&sig,'('); break; case ')': while (sig.data[sig.top-1]!='(') { PopSign(&sig,&es); Calculate(&Num,es); } PopSign(&sig,&es); } } } while (sig.top>0) { PopSign(&sig,&es); Calculate(&Num,es); } GetTopNumber(Num,&en); printf("%.0f\n",en); return 0; } void InitNumber(number *stack) { stack->top=0; } void GetTopNumber(number stack, float *e) { if(stack.top==0) return; else *e=stack.data[stack.top-1]; } void PushNumber(number *stack, float e) { if(stack->top>=maximum) return; else stack->data[stack->top++]=e; } void PopNumber(number *stack, float *e) { if(stack->top==0) return; else *e=stack->data[--stack->top]; } void InitSign(sign *stack) { stack->top=0; } void GetTopSign(sign stack, char *e) { if(stack.top==0) return; else *e=stack.data[stack.top-1]; } void PushSign(sign *stack, char e) { if(stack->top>=maximum) return;//栈满 else { stack->data[stack->top]=e; stack->top++; } } void PopSign(sign *stack, char *e) { if(stack->top==0) return; else *e=stack->data[--stack->top]; } void Calculate(number *stack, char e)// 计算结果 { float num1,num2,result; PopNumber(stack, &num2); PopNumber(stack, &num1); switch (e) { case '+': result=num1+num2; PushNumber(stack,result); break; case '-': result=num1-num2; PushNumber(stack,result); break; case '*': result=num1*num2; PushNumber(stack,result); break; case '/': if (num2==0) printf("表达式错误！"); else { result=num1/num2; PushNumber(stack,result); break; } case '^': result=pow(num1,num2); PushNumber(stack,result); break; } }
如果每个操作符跟在它的两个操作数之后，而不是两个操作数之间，那么这个表达式就是后缀表达，又称为逆波兰表达式，如：3 5 + 7 * 1 - 2.后缀表达式计算机求值1.与前缀表达式类似，只是顺序是从左至右： 2.从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，其中先出栈的是右操作数，后出栈的是左操作数， 3.用运算符对它们做相应的计算（次顶元素 op 栈顶元素），并将结果入栈； 4.重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果 3.例子计算后缀表达式的值：1 2 3 + 4 × + 5 - 1）从左至右扫描，将1，2，3压入栈； 2）遇到+运算符，3和2弹出，计算2+3的值，得到5，将5压入栈； 3）遇到4，将4压入栈 4）遇到×运算符，弹出4和5，计算5×4的值，得到20，将20压入栈； 5）遇到+运算符，弹出20和1，计算1+20的值，得到21，将21压入栈； 6）遇到5，将5压入栈； 7）遇到-运算符，弹出5和21，计算21-5的值，得到16为最终结果 4.代码实现 bool isNumber(char* token) { return strlen(token) > 1 || ('0' next=S; //将结点s作为链栈的栈顶结点 S=s; //栈顶指针S指向结点s return true; } bool Pop(LiStack &S,char &x){ //栈顶元素出栈，将值赋给x if(S==NULL) return false; //栈空则返回NULL x=S->data; Linknode *p=S; S=S->next; free(p); return true; } int main(){ char temp,a[size],b[size]; //静态数组a、b分别存放要转换的中缀表达式和转换后的后缀表达式,字符变量temp存放弹出的栈顶元素 scanf("%s",&a); //需要您输入中缀表达式 LiStack S;//初始化一个栈，用于保存括号和暂时还不能确定运算顺序的运算符 InitStack(S); //初始化链栈 int i,j,length=strlen(a); //length为输入的中缀表达式的总长度，i、j分别为静态数组a、b的索引下标 for(i=j=0;i=48 && a[i] |
【本文地址】