(作业本P71)四则运算式转逆波兰式。为便于利用栈求解四则运算式的值,需要将其转化为逆波兰式,如四则运算式“6+(8-2)*2/3”转化为逆波兰式的结果为“682-2*3/+”。小明设计算法,输入四则运算式,输出其逆波兰式。
算法设计:
步骤 1:定义运算符的优先级,用数字表示运算符的优先级,数字越小表示优先级越高。
步骤2:依次读取四则运算式的每个字符,若是运算对象,直接加入输出结果中。
若是运算符,根据运算符的优先级确定是否对栈内的运算符进行出栈操作:若是栈顶运算符的优先级低进行进栈操作;
若是栈顶运算符的优先级高于或与当前运算符的优先级相同,则不断进行出栈操作,直到栈顶运算符的优先级低于当前读取到的运算符。
两种特殊的情况:
a.若栈是空的或者是“(”,则直接进栈;
b.若当前读取到的运算符是“)”,则不断出栈,将运算符加入输出结果中,直到遇到最后进栈的“(”,并将该“(”出栈
步骤3:最后将栈中出栈的运算符出栈后依次加入输出结果中。