急求!!用数据结构的堆栈做出
发布网友
发布时间：2024-07-03 21:50
共1个回答
热心网友
时间：2024-07-04 19:15
2 表达式计算
2.1 算符优先分析
算符优先分析是定义算符之间的某种优先关系，这种关系可以为表示以下三种：
a＜ba的优先性低于b
a＝ba的优先性等于b
a＞ba的优先性高于b
其中a和b代表一种算符，＜、＝和＞不同于数学里的大于、等于和小于，同时a＜b并不代表b＞a, a＝b并不代表b＝a。
2.2 表达式表示
在机器内部，任何一个表达式都是由操作数、运算符和分界符组成，分界符表示一个表达式的结束。假设在此讨论的算符只含加、减、乘、除四种算术运算符和左、右圆括号。如一个算术表达式A+(B-C/D)*E，这种算术表达式中的运算符一般总是出现在两个操作数之间称中缀表达式。在计算机的编译系统中，在处理中缀表达式之前，总是先将它变换成后缀表达式，即表达式中的运算符出现在操作数之后，且不含括号。把一个中缀表达式变换成相应的后缀表达式首先考虑运算规则。算术运算的规则是：(1)先乘除后加减；(2)先括号内后括号外；(3)同级别时先左后右。则上面中缀表达式可写成ABCD/-E*+，由此可知后缀表达式的两个特点：(1)后缀表达式与中缀表达式的操作数先后次序相同，只是运算符的先后次序有所变化。后缀表达式的运算符次序就是其执行次序；(2)后缀表达式没有括号（如表1）。
表1 后缀表达式的处理过程
2.3 算符优先关系
由后缀表达式特点(1)知，后缀表达式与中缀表达式的操作数排列次序相同，只是运算符改变了次序。编译系统从左到右依次扫描中缀表达式，每读到一个操作数即将它作为后缀表达式的一部分输出。系统设置一个存放运算符的栈，初始时栈顶置一分界符#，并将其也看作运算符。每读到一个运算符，就将其优先级与栈顶位置运算符优先级进行比较，以决定是把所读的运算符进栈还是将栈顶位置的运算符作为后缀表达式的一部分输出。表2给出了包括加、减、乘、除四种算术运算符和左、右圆括号和分界符的算术运算符间的优先级关系表。表中θ1代表栈顶运算符，θ2代表当前扫描读到的运算符。
表2 运算符优先级关系
表2是四则运算三条规则的变形。对规则(1)，当θ1为+或-，θ2为*或/时，θ1的优先级低于θ2的优先级（先乘除后加减）；对规则(2)，θ1当为+、-、*或/，θ2为（时，θ1的优先级低于θ2的优先级（先括号内后括号外）；当θ1为+、-、*或/，θ2为）时，θ1的优先级高于θ2的优先级（先求出括号内的值）；对规则(3)，当θ1的运算符和θ2的运算符同优先级别时，令θ1的优先级高（同级别时先左后右）。由于后缀表达式无括号，当θ1为（，θ2为）时，用符号”=”表示去掉该对括号。当θ1为#时，θ2也为#时，表示整个表达式处理完毕。表2中空格处表示不允许出现这种情况，一旦出现，即为中缀表达式语法出错。
2.4 表达式计算
中缀表达式变换成相应的后缀表达式后，根据后缀表达式计算表达式的值方法为：设置一个足够大的堆栈，从前向后依次扫描后缀表达式，每读到一个操作数，就将其压入堆栈；每读到一个运算符，就从栈顶取出两个操作数施以该运算符所代表的操作，并把计算结果作为一个新的操作数压入堆栈，一直到后缀表达式读完。最后在栈顶位置的操作数就是该算术表达式的计算结果。
3 算法实现
#include
char newstr[20]; int p=0;
char proceed(char x1,char x2) /*算符比较*/
{char result1;
char Midstring[2];
result1='<';Midstring[0]=x2; Midstring[1]='\0';
if(((x1=='+'||x1=='-')&&strstr("+-)#",Midstring)!=-1)
||((x1=='*'||x1=='/')&&strstr("+-*/)#",Midstring)!=-1)
||(x1==')'&&strstr("+-*/)#",Midstring)!=-1))
result1='>';
else if((x1=='(' && x2==')')||(x1=='#' && x2=='#'))
result1='=';
else if((x1=='(' && x2=='#')||(x1==')' && x2=='(')||(x1=='#' && x2==')'))
result1=' ';
return(result1);}
int strstr(char str1[],char str2[])
{int i,j,k,m,n;
char tempStr1,tempStr2;
m=strlen(str1);
n=strlen(str2);
for(i=0;i {k=i;
for(j=0;j<1;j++,k++)
{tempStr1=str1[k];
tempStr2=str2[j];
if(tempStr1==tempStr2)
continue;
else break;}
if(j>=n) return(1);}
return(-1);}
/*中缀表达式变换后缀表达式*/
intprotfix(char str[])
{char stack[20];
char x1,x2,x;
int j=0,k=0;
stack[0]='#';
x2=str[j];
x1=stack[0];
while(1)
{if(x2!='+'&&x2!='-'&&x2!='*'&&x2!='/'&&x2!='('&&x2!=')'&&x2!='#')
{newstr[p++]=x2;
j++;x2=str[j];}
else
本文原文
if(proceed(x1,x2)=='<')
{stack[++k]=x2;
x1=stack[k];
j++; x2=str[j];
}else if(proceed(x1,x2)=='>')
{ x=stack[k--];
newstr[p++]=x;
x1=stack[k];}
else if(proceed(x1,x2)=='='&&x1=='('&&x2==')')
{k--;x1=stack[k];
j++;x2=str[j]; }
Else
if(proceed(x1,x2)=='='&&x1=='#'&&x2=='#')
return(1);
else if(proceed(x1,x2)= =' ')
break;}
return(0);}
double count(char str[])/*计算表达式的值*/
{double x1,x2,x; int a,i=0;
while(str[i]!='\0')
{if(isdigit(str[i]))
push(str[i]-48);
else
Switch(str[i])
{case '+': x1=pop();x2=pop();
x=x1+x2;push(x);break;
case '-': x1=pop();x2=pop();
x=x1-x2;push(x);break;
case '*': x1=pop();x2=pop();
x=x1*x2;push(x);break;
case '/': x1=pop();x2=pop();
x=x1/x2; push(x); break; }
i++;}}
return(x);}
4 结束语
表达式计算作为程序设计语言的基础，是高级程序设计语言学习者和程序员必备的基础知识，本文通过算符优先分析和堆栈的方法，给出了算术表达式的计算过程，同时给出了算法描述，有助于高级语言初学者和计算机编程人员熟悉计算机内部表达式计算的处理过程，更好地学习和掌握高级语言的编程技术。
