您现在的位置是：首页 > 后台技术 > 数据结构与算法数据结构与算法

前缀，中缀，后缀表达式(图文)

第十三双眼睛2022-06-13【数据结构与算法】人已围观

简介前缀，中缀，后缀表达式

前缀表达式，又称为波兰表达市，后缀表达式又称为逆波兰表达式。中缀表达式就是人最容易理解的表达式。
前缀表达式的计算机求值
符号在前面，数字在后的，叫做前缀表达式，运算方法：从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，运算完毕后入栈，重复上述过程直到表达式最左端，最后运算得出的结果即为
表达式的值。
后缀表达式的计算机求值
符号在后，数字在前的，叫做后缀表达式，运算方法：从左到右扫描表达式，遇到数字时，压入栈中，遇到运算符时，弹出两个数，运算完毕后，将运算结果入栈，重复上述过程直到表达式的最右段，最后运算得出的结果即为表达式的值。
中缀表达式：就是我们正常见到的运算表达式，运算符在数字中间。
逆波兰计算器

package day003;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class Poland {
public static void main(String[] args) {
String expression = "3 4 + 5 * 6 -";
List<String> list = getList(expression);
int res = calc(list);
System.out.println("计算的结果是：" + res);
}
public static List<String> getList(String expression){
String[] split = expression.split(" ");
List<String> list = new ArrayList<>();
for(String s: split){
list.add(s);
}
return list;
}
public static int calc(List<String> list){
Stack<String> stack = new Stack<String>();
for(String string: list){
if(string.matches("\\d+")){
stack.push(string);
}else {
int num2 = Integer.parseInt(stack.pop());
int num1 = Integer.parseInt(stack.pop());
int res = 0;
if("+".equals(string)){
res = num1 + num2;
}else if("-".equals(string)){
res = num1 - num2;
}else if("*".equals(string)){
res = num1 * num2;
}else{
res = num1 / num2;
}
stack.push(res +"");
}
}
return Integer.parseInt(stack.pop());
}
}

后缀表达式有利于计算机但是人不方便操作，因此在开发中，需要将中缀表达式转换为后缀表达式。
中缀表达式转后缀表达式思路：
1初始化两个栈，存放运算符的栈s1和存放中间结果的栈s2
2从左到右扫描中缀表达式
3遇到操作数时，压入s2栈
4遇到运算符时，比较其与s1栈顶的运算符优先级
4.1如果s1为空或者s1栈顶为左括号"(",则直接将运算符入栈
4.2如果运算符的优先级比s1栈顶运算符优先级高，则直接将运算符入栈
4.3如果运算符的优先级比s1栈顶运算符优先级低，则将栈顶运算符弹出，并压入s2栈中，并转向4
5遇到括号时，
5.1如果遇到的是左括号，则直接压入s1栈中
5.2如果是右括号，则将s1栈中的运算符弹出并压入s2，知道遇到左括号，此时，消除一对括号。
6重复步骤2-5，知道表达式的最右边
7将s1中的剩余的运算符弹出并压入栈s2中
8依次弹出s2栈中的元素，并输出，结果的逆序即为中缀表达式对应的后缀表达式。
程序代码如下：

package day003;
public class Operation {
private static int ADD = 1;
private static int SUB = 1;
private static int MUl = 2;
private static int DIV = 2;
public static int getValue(String value){
int result = 0;
switch (value){
case "+":
result = ADD;
break;
case "-":
result = SUB;
break;
case "*":
result = MUl;
break;
case "/":
result = DIV;
break;
default:
break;
}
return result;
}
}

package day003;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class InToSufixx {
public static void main(String[] args) {
String expression = "1+((2+3)*4)-5";
List<String> list = toSuffix(expression);
List<String> parse = parse(list);
System.out.println(parse);
}
public static List<String> parse(List<String> list){
Stack<String> s1 = new Stack<String>();
List<String> s2 = new ArrayList<>();
for(String item: list){
if(item.matches("\\d+")){
s2.add(item);
}else if("(".equals(item)){
s1.push(item);
}else if(")".equals(item)){
while (!s1.peek().equals("(")){
s2.add(s1.pop());
}
s1.pop();
}else{
while (s1.size()!=0&& Operation.getValue(s1.peek())>=Operation.getValue(item)){
s2.add(s1.pop());
}
s1.push(item);
}
}
while (s1.size()!=0){
s2.add(s1.pop());
}
return s2;
}
public static List<String> toSuffix(String expression){
List<String> list = new ArrayList<>();
int i = 0;
String str = "";
char c;
do{
c = expression.charAt(i);
if(c< 48 || c> 57){
list.add(c +"");
i++;
}else{
str = "";
while (i<expression.length()&&(c = expression.charAt(i))>=48 && (c = expression.charAt(i))<=57){
str += c;
i++;
}
list.add(str);
}
}while (i<expression.length());
return list;
}
}

测试一下：1+((2+3)*4)-5
结果为：1, 2, 3, +, 4, *, +, 5, -

Tags：

很赞哦！ ()

上一篇：使用栈实现综合计算器(图文)

下一篇：递归(图文)