C++:前缀、中缀、后缀表达式互相转换详解 |
您所在的位置:网站首页 › 前缀表达式算法思想 › C++:前缀、中缀、后缀表达式互相转换详解 |
文章目录
中缀表达式 转为 前缀表达式(波兰式)前缀表达式 逆向求解 中缀表达式
中缀表达式 转为 后缀表达式(逆波兰式)后缀表达式 逆向求解 中缀表达式图解示例:代码实现:
一个中缀式到其他式子的转换方法(超级简易)~~相关习题:
表达式定义示例前缀表达式运算符位于操作数之前- × + 3 4 5 6中缀表达式操作符以中缀形式处于操作数的中间(3 + 4) × 5 - 6后缀表达式运算符位于操作数之后3 4 + 5 × 6 -
前缀式,后缀式是不需要用括号来进行优先级的确定的。 中缀表达式 转为 前缀表达式(波兰式)遵循以下步骤: 初始化两个栈:运算符栈S1和储存中间结果的栈S2;从右至左扫描中缀表达式;遇到操作数时,将其压入S2;遇到运算符时,比较其与S1栈顶运算符的优先级: 4.1 如果S1为空,或栈顶运算符为右括号“)”,则直接将此运算符入栈; 4.2 否则,若优先级比栈顶运算符的较高或相等,也将运算符压入S1; 4.3 否则,将S1栈顶的运算符弹出并压入到S2中,再次转到(4-1)与S1中新的栈顶运算符相比较遇到括号时: 5.1 如果是右括号“)”,则直接压入S1; 5.2 如果是左括号“(”,则依次弹出S1栈顶的运算符,并压入S2,直到遇到右括号为止,此时将这一对括号丢弃重复步骤(2)至(5),直到表达式的最左边;将S1中剩余的运算符依次弹出并压入S2;依次弹出S2中的元素并输出,结果即为中缀表达式对应的前缀表达式。 前缀表达式 逆向求解 中缀表达式-+1*+2345 思路: 递归,碰到操作符就进入递归。 从右往左扫描先碰到+号,取+号后面两个操作数:2,3 得到:2+3.继续往左扫碰到*号,取2+3和 4 得到:(2+3)*4继续往左扫碰到+号,取1和(2+3)*4得到:1+(2+3)*4继续往左扫碰到-号,取1+(2+3)*4和5得到:1+(2+3)*4-5 中缀表达式 转为 后缀表达式(逆波兰式)与转换为前缀表达式相似,遵循以下步骤: 初始化两个栈:运算符栈S1和储存中间结果的栈S2;从左至右扫描中缀表达式;遇到操作数时,将其压入S2;遇到运算符时,比较其与S1栈顶运算符的优先级: 4.1 如果S1为空,或栈顶运算符为左括号“(”,则直接将此运算符入栈; 4.2 比栈顶高,也将运算符压入S1 (注意转换为前缀表达式时是优先级较高或相同,而这里则不包括相同的情况); 4.3 比栈顶低或相同,将S1栈顶的运算符弹出并压入到S2中,再次转到(4-1)与S1中新的栈顶运算符相比较;遇到括号时: 5.1 如果是左括号“(”,则直接压入S1; 5.2 如果是右括号“)”,则依次弹出S1栈顶的运算符,并压入S2,直到遇到左括号为止,此时将这一对括号丢弃; 可以想象成“(”比任何运算符都高,“)”比任何运算符都低。重复步骤(2)至(5),直到表达式的最右边;将S1中剩余的运算符依次弹出并压入S2;依次弹出S2中的元素并输出,结果的逆序即为中缀表达式对应的后缀表达式(转换为前缀表达式时不用逆序)。 后缀表达式 逆向求解 中缀表达式1 2 3 + 4* 5 - + 基本思路和上面的一样: 递归,碰到操作符就进入递归 从左往右扫描先碰到+号,取+号前面两个操作数:2,3 得到:2+3.继续往右扫碰到*号,取2+3 和 4 得到:(2+3)*4继续往右扫碰到-号,取(2+3)*4和5得到:(2+3)*4-5继续往右扫碰到+号:取(2+3)*4-5和1得到:1+(2+3)*4-5 图解示例:前缀表达式为:-+1*+2345 中缀转后缀:(直接转换法)首先确定表达式表达式A的运算顺序,然后加括号:((1 + (( 2 + 3)* 4 )) – 5 ) 从最里面的一层括号开始运算,转换成后缀表达式的方法为:(忽略括号)数字在前,符号在后。 演示过程如下: ( 2 + 3) => 23+(( 2 + 3)* 4 ) => 23+4*(1 + (( 2 + 3)* 4 ))=> 123+4*+ [按照运算次序,从左到右排列]((1 + (( 2 + 3)* 4 )) – 5 )=> 123+4*+ 5-后缀表达式为:123 + 4*+ 5 – |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |