文章堆栈应用的公式评价问题1——无括号公式评价实现代码问题2——有括号公式评价实现代码
评估应用于堆栈的公式
公式的评价也是堆栈的经典应用之一。 对于表达式的计算,可以转换为后缀表达式,然后计算值。
有关从骑马订表达式到后缀表达式的转换,请参阅文章中从后缀表达式到后缀表达式的转换过程
使用后缀计算表达式的值如下所示:
a .如果该项为操作数,则推入堆栈;
b .此项为操作符时,将两个操作数y和x连续退出堆栈,生成运算指令XY,将计算机结果重新推入堆栈。 当公式中的所有项目都被扫描和处理后,最后一个计算结果将存储在堆栈的顶部。
优化:在骑马订表达式成为后缀表达式的过程中,可以边转换边计算。
具体步骤如下。
首先,必须分配两个堆栈:作为临时存储运算符的堆栈S1 (终结符‘#’和存储结果的堆栈S2 )。
从左向右依次扫描骑马订式,
如果检索到的字符是操作数,则直接发送到堆栈S2,如果检索到的字符是运算符:
如果是a .则为’’,堆栈S1;
b .’)’时,依次将堆栈内的运算符添加到后缀表达式中,从堆栈S2中各取出两个操作数,进行当前运算,将运算结果推入堆栈S2,直到’’出现。 ’’;
c .对于非括号运算符,如果其优先级为高于堆栈顶部的运算符,则直接进入堆栈; 否则,从堆栈的开头开始,依次调用小于当前正在处理的运算符优先级高和优先级相等的运算符,从堆栈S2各取出两个操作数,进行当前运算,遇到优先级比其低的运算结果,或者向左
问题——对不存在括号的公式的评价括号不存在的公式进行计算。
输入说明:
存在多个数据,每组数据一行,表达式中不存在空格
输出说明:
输出计算结果
示例:
输入:
6/2 3 3*4
输出:
18
实现代码的完整代码:
# include bits/stdc.husingnamespacestd; //数字浮动编号(strings,int index ) {浮动编号=0; while(isdigit(s[index] ) { number=number * 10 s[index] - '0'; 索引; }返回编号; //优先级intpriority(charc ) if ) c=='# ' ) { return 0; }elseif(c=='$ ' ) /将表达式末尾的特殊运算符设置为以下低,如果遍历表达式末尾时S1堆栈中还有可运算的符号,则继续进行运算; //S1即使堆栈中只剩下特殊符号#,也能确保$顺利进入堆栈,正确结束程序! //我最初设定的S1和式末尾的特殊符号都是#,结果是无限循环,到结束为止#都没能正确堆栈。 返回1; }elseif(c==''||c=='-' ) { return 2; (else(/)、/return 3; }//floatcalculate(floatx、float y、char c ) { float result=0; if(c==' ' ) { result=x y; }elseif(c=='-' ) { result=x - y; }elseif(c=='* ' ) { result=x * y; }elseif(c=='/' ) { result=x/y; }返回结果; (}int main ) ) { string s; wile (获取行(CIN,s ) ) { int index=0; //字符串下标stackchar S1; 堆栈浮动S2; s ='$ '; //在字符串末尾添加$s1.push('# ' ); //堆栈S1堆栈底部包含#while(indexs.size () if (isdigit ) s[index] ) /操作数S2.push (getnumber ) s,index ) ) //取出操作数,推入堆栈S2//coutS2.top () endl; } else { if (优先级) S1.top ) (优先级) s [索引] )//高优先级,推入堆栈S1
S1.push(s[index]);// cout<<S1.top()<<endl; index++; }else{ //否则出栈进行计算,计算结果压入栈S2 float y = S2.top(); S2.pop(); float x = S2.top(); S2.pop(); S2.push(calculate(x,y,S1.top())); S1.pop(); } }//else } cout<<fixed<<setprecision(2)<<S2.top()<<endl; } return 0;}问题二——存在括号的表达式求值
对于一个存在括号的表达式进行计算。
输入描述:
存在多种数据,每组数据一行,表达式不存在空格
输出描述:
第一行输出后缀表达式,第二行输出计算结果
示例:
输入:
((6/2)+3+(3*4))
输出:
6 2 / 3 + 3 4 * +
18