首页 > 编程知识 正文

表达式求值问题,蓝桥杯有必要参加吗

时间:2023-05-04 23:51:16 阅读:22372 作者:2706

最近要参加免试研究生复试,准备遭遇上机考试。 没办法啊。 令人气愤的是,网络上的很多方法都是错误的,最终做出了比较正确的东西。问题描述

输入只包含加减法和括号的正则表达式,以获得表达式的值。 其中除法意味着整除。

输入格式

输入包含公式的行。

输出格式

输出此表达式的值。

样本输入

1-2 3*(4-5)

样本输出

-4 数据规模和约定

表达式的长度不超过100,表达式的运算合法,运算处理均在int内进行。

1 .如何将骑马订格式转换为后缀格式:

(1)初始化运算符堆栈S1和存储中间结果的堆栈S2这2个堆栈;

(2)自左向右扫描骑马订式;

)3)遇到操作数时,将其推入S2。 在此,由于操作数可能大于10,因此如果数字后面的符号是运算符,则将“#”放入S2堆栈中用作分割线。

)4)遇到运算符时,有三种情况。

(4-1) 3种情况下,直接进入S1堆栈S1为空运算符为‘)运算符的优先级高于S1堆栈顶部运算符

(4-2)方括号“)”时,依次弹出S1堆栈顶部的运算符,按S2直到遇到方括号。 此时,放弃这个括号对。

(4-3)当运算符优先顺序小于或等于S1堆栈顶部运算符的优先顺序时,依次弹出S1堆栈顶部元素,直到运算符的优先顺序大于S1堆栈顶部运算符的优先顺序;

重复(6)顺序(2)到(5)直到公式的最右边。

(7)依次弹出S1中剩下的运算符,推入S2;

)8)依次弹出S2的要素输出,结果的逆序为与骑马订式相对应的后缀式。

例:将1 () 2334 )5)- 6改为骑马订式所以计算结果为:1 # 2 3 # 3 4 # + 5 # * + 6 # -

2 .后缀表达式计算方法:

)1)定义int堆栈S3,定义整形数组num,存储大于10的数字以便于计算,然后从左向右扫描公式。

)2)遇到数字时:

(2-1)如果数字后面的元素不是# ()数字后面只有#或数字) )将数字字符转换为数字并存在于num )数组中;

(2-2)数字的下一个要素为#时,计算保存在num数组中的数字并推入S3堆栈。

)3)遇到运算符时,弹出S3栈顶的两个个数,用运算符正确计算它们,并将结果放入栈中; 重复上述步骤直到公式的右端,最后运算出的值即为公式的结果。

例如后缀表达式“1 # 2 3 # 3 4 # + 5 # * + 6 # -”:

所以最后计算的结果是280

# include stdio.h # include algorithm # include iostream # includestackusingnamespacestd; intBB0(inta、int b、char c ) /运算(if ) c==' ' )返回a b; if(c=='-' )返回a-b; if(c=='* ' )返回a* b; if(c=='/' )返回a/b; }voidBB1(constchar*a、char *b、char *c ) intk=0,l=0,flag=0; for(intI=0; a[i]!=' '; I//扫描字符串(if(a[I]='0'a[I]='9' ) ) /如果是数字,则为b堆栈({ b[k ]=a[i]; if(a[I1]'0'|a[I1]'9' ) /如果以下字符是运算符,则#b堆栈b[k ]='# '; }elseif(a(I )==' ) ) ) /右括号)对于while(c(-l )!=' ' () ) { b[k ]=c[l]; } } else//运算符(if ) L0 )/C堆栈中有元素,比较优先级(if(a(I )=('|a(I )='-' ) ) /扫描运算符为-{while ) c(L-1} )=''L0(/堆栈顶部元素为(b ) k )=C(-L ); //c堆栈到b堆栈}}if(a[I]=='*'|a[I]=='/' ) /扫描的是*,/(if (c [ I-1 ]=' * '|c [ I ] //扫描运算符进入c堆栈}}while(L0 )//c堆栈中如果还有元素,则全部进入b堆栈(b ) k )=C(-L ); } b[k]=' '; }voidBB2(char*b,int *d ) /后缀表达式计算(intc=0,l=0; for(intI=0; b[i]!=' '; I(/扫描后缀表达式(if ) b ) I )='9) b )='0) ) /对于数字(c=c*10 ) b ) I )-'0); //原始数字*10如果为当前数字(elseif ) b[I]='# ' ) /,则为# { d[l ]=c; //数字进d堆栈c=0; //清除缓冲区数组} else//运算符{d[l-2]=bb0(d[l-2],d[l - 1],b[i] ); //子顶元素op堆栈顶元素,结果进入d堆栈l=l - 1; //d堆栈长度-1,(两个数合二为一) }(intmain ) { char a[105]; //输入的字符串堆栈通道mid re; 堆栈字符操作器; char b[105]={ ' ' }; //中间结果堆栈char c[100]={ ' ' }; //运算符堆栈int d[50]; cin a; B1(A、b、c ); //BB1(a,midre,opera ); B2(B,d ); //bb2 ) cout d[0] endl; 返回0; }

版权声明:该文观点仅代表作者本人。处理文章:请发送邮件至 三1五14八八95#扣扣.com 举报,一经查实,本站将立刻删除。