1.四则运算
输入一个表达式（用字符串表示），求这个表达式的值。
保证字符串中的有效字符包括[‘0’-‘9’],‘+’,‘-’, ‘*’,‘/’ ,‘(’， ‘)’,‘[’, ‘]’,‘{’ ,‘}’。且表达式一定合法。
示例：
输入： 3+2{1+2[-4/(8-6)+7]}
输出： 25
解题思路： 逆波兰表达式
1)初始化两个栈，运算符栈s1, 数据栈s2 (将此栈定义为集合)
2）从左到右扫描中缀表达式
3）遇到操作数，将其压入s2
4)遇到用算符，比较其与s1栈顶元素的优先级：
1.如果s1为空，或者栈顶运算符为 "( || [ || {",直接压入栈中
2.否则，优先级比栈顶元素优先级高也压入s1中，
3.否则，将s1中用算符弹出压入s2,再转到 4.1中执行
5) 遇到括号时：
如果为左括号："( || [ || {"，直接压入s1
如果为右括号: ") || ] || }", 依次弹出s1中运算符，并压入s2,直到遇到对应的左括号为止，此时丢弃这对括号
6) 重复步骤2至5，直到表达式最右边
7）将s1中剩余的运算符依次弹出压入s2
8) s2即为后缀表达式
负数的处理：
出现负数有两种情况：
①： 表达式第一个就为 '-' 号，则判定此数为负数 如：-3+1
②： 表达式中'-'的前一个符号为左括号'(',则判定 此数为负数 如： （-3+1）
转化方法在前面补0即可如： 0-3+1；
代码：
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
str = str.replaceAll("[\{\[]", "(").replaceAll("[\}\]]",")"); //将中缀表达式中的括号转为小括号
List<String> l1 = strToList(str);
List<String> l2 = zToH(l1);
int num = getNum(l2);
System.out.println(num);
}
// 计算后缀表达式
private static int getNum(List<String> ls) {
Stack<String> s1 = new Stack<>();
for (String s : ls) {
if (s.matches("\d+")) {
// 如果为数字压入到s1中
s1.push(s);
} else {
// 如果不为数字，从栈中弹出两个数字，进行计算，再压入栈中
int num1 = Integer.parseInt(s1.pop());
int num2 = Integer.parseInt(s1.pop());
int num = cal(num1, num2, s);
s1.push(String.valueOf(num));
}
}
return Integer.parseInt(s1.pop());
}
//计算结果
private static int cal(int num1, int num2, String oper) {
int val = 0;
switch(oper) {
case "+":
val = num2 + num1;
break;
case "-":
val = num2 - num1;
break;
case "*":
val = num2 * num1;
break;
case "/":
val = num2 / num1;
break;
}
return val;
}
// 将中缀表达式转化为后缀表达式
private static List<String> zToH(List<String> ls) {
Stack<String> s1 = new Stack<>(); // 存储字符
List<String> s2 = new ArrayList<>(); //存储数字
int i=0;
for (String s : ls) {
if (s.matches("\d+")) {
// 如果为数字，直接添加到s2中
s2.add(s);
} else if (s1.size() ==0 || "(".equals(s) || "(".equals(s1.peek())) {
// 处理负数， 负数有两种情况
// 1. 负数存在与第一位如： -3+1
//2.负数存在与左括号后面： (-3+1)
// 处理方法为在前面补0如： 0-3+1
if("-".equals(s) && (i == 0 || "(".equals(ls.get(i-1)))) {
s2.add("0");
}
s1.push(s);
} else if (")".equals(s)) {
// 如果遇到右括号')'，依次弹出s1直到遇到左括号'('
while(!"(".equals(s1.peek())) {
s2.add(s1.pop());
}
s1.pop(); //弹出左括号
} else {
// 如果栈顶也为 ‘+，-，*，/’，需要比较优先级。
//若s的优先级小于等于栈顶元素，s1弹出插入到s2中
// 否则，将s压入到s1中
while(s1.size() != 0 && isLeve(s) <= isLeve(s1.peek())) {
s2.add(s1.pop());
}
s1.push(s);
}
i++;
}
// 将s1中剩余的符号插入到s2中
while(s1.size() != 0) {
s2.add(s1.pop());
}
return s2;
}
// 判断优先级
private static int isLeve(String str) {
if ("+,-".contains(str)) {
return 1;
} else if("*,/".contains(str)) {
return 2;
} else {
return 0;
}
}
// 将中缀表达式转为字符串数组
private static List<String> strToList(String str) {
char[] chars = str.toCharArray();
List<String> ls = new ArrayList<>();
int i = 0;
String s = "";
for (char ch: chars) {
if (ch<48 || ch >57) {
// 如果不是数字直接添加到集合中
ls.add(ch + "");
} else {
// 如果为数字，则需要处理，因为数字可能为多位数
s += ch; //数字拼接起来
if (i == str.length()-1) {
// 如果当前字符串为最后一个则直接添加
ls.add(s);
} else {
if (chars[i+1] <48 || chars[i+1] >57) {
ls.add(s);
s = "";
}
}
}
i++;
}
return ls;
}
}