中缀转后缀
思路
中缀表达式转后缀表达式
1.首先初始化两个栈s1,s2,一个存放数字,一个存放符号
2.从左向右扫描中缀表达式 Expression
3.遇到数字直接压入栈s2,遇到运算符则与s1栈顶运算符比较优先级
3.1 符号为左括号,符号栈S1为空,扫描到的运算符的优先级比s1栈顶元素优先级高 ,直接入栈s1
3.2 符号为右括号,扫描到的运算符的优先级比s1栈顶元素优先级低,将s1栈顶元素弹出,并压入s2,重复3的操作
4.遇到括号
4.1符号为左括号,直接入栈
4.2 符号为右括号,将符号栈中元素出栈,并压入栈s1,直到遇到左括号为止,然后对其这一对括号
5.重复3,4操作,直到表达式最右边
6.将s1中剩余运算符依次弹出,并压入s2
7.依次弹出s2中的元素并输出,结果的逆序为中缀表达式对应的后缀表达式
代码实现
public static List<String> toInfixExpressionList(String s){
List<String> ls = new ArrayList<>();
int i = 0 ;//用来遍历字符串
String str ; //对多位数进行拼接
char c ; //每遍历到字符,就放入c中
do {
//如果c 是一个非数字,就需要加入到ls
if((c=s.charAt(i)) < 48 || (c=s.charAt(i))>57){
ls.add(""+c);
i++;
}else {
//是多位数数字就需要拼接
str="";//重置str
while(i<s.length() && (c=s.charAt(i)) >= 48 && (c=s.charAt(i))<=57){
str += c;
i++;
}
ls.add(str);
}
}while (i < s.length());
return ls;
}
//编写一个类,返回运算符对应的优先级
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 operation){
int result = 0;
switch(operation){
case "+":
result = ADD;
break;
case "-":
result = SUB;
break;
case "*":
result = MUL;
break;
case "/":
result = DIV;
break;
default :
throw new RuntimeException("没有这个运算符");
}
return result;
}
}
后缀表达式的计算
思路
1.先将 表达式放入ArrayList中
2.将ArrayList 传递给一个方法,遍历ArrayList 配合栈 完成计算
3.将一个逆波兰表达式,依次放入到 ArrayList中
遍历ArrayList,当遇到数字就入栈,遇到操作符就从栈中pop弹出连个元素,并进行运算,得到的结果在入栈
当遍历玩表达式,栈中只有一个元素就是想要的结果
public static int inversePolishCalculator(String suffixExpression){
//先将字符串 分割,放入ArrayList中
String[] split = suffixExpression.split(" ");
List<String> list = new ArrayList<>();
for (String ele: split) {
list.add(ele);
}
//完成对逆波兰表达式的计算
//先创建一个栈
Stack<String> stack = new Stack<>();
//遍历ArrayList
for (String item:list) {
//使用正则表达式来取出数
if(item.matches("\\d+")){
//匹配的是多位数 ,入栈
stack.push(item);
}else{//不是多位数
//pop 出两个数并运算
int num2 = Integer.parseInt(stack.pop());
int num1 = Integer.parseInt(stack.pop());
int res = 0;
if(item.equals("+")){
res = num1 + num2;
}else if(item.equals("-")){
res = num1 - num2;
}else if(item.equals("*")){
res = num1 * num2;
}else if (item.equals("/")) {
res = num1 / num2;
} else {
throw new RuntimeException("运算符异常");
}
//将res入栈
stack.push(""+ res);
}
}
//最后栈中的数就是所需结果
return Integer.parseInt(stack.pop());
}
测试
public static void main(String[] args) {
// //为了方便,逆波兰表达式数字与符号用空格隔开
// String suffixExpression = "3 4 + 5 * 6 -";
// int res = inversePolishCalculator(suffixExpression);
// System.out.printf("表达式:%s = %d",suffixExpression, res);
String expression= "1+((200+3)*4)-5";
List<String> expressionList = toInfixExpressionList(expression);
System.out.println(expressionList);
List<String> list = infixToSuffix(expression);
System.out.println(list);
}