- 一、算法描述
- 二、个人分析
- 三、代码实现
- 四、基础知识
- 栈（stock）
- 前缀表达式
- 中缀表达式
- 后缀表达式（逆波兰表达式）
一、算法描述
该题是牛客网-华为机试 51题给定一个字符串描述的算术表达式，计算出结果值。输入字符串长度不超过 100 ，合法的字符包括 ” , -, *, /, (, )” ， ”0-9” 。数据范围：运算过程中和最终结果均满足 |val| \le 2^{31}-1 ，即只进行整型运算，确保输入的表达式合法
输入描述：输入算术表达式
输出描述：计算出结果值
示例1输入：400 5复制输出：405
二、个人分析
这道题主要考察的知识点为字符串、栈、基础数学。1.将输入的表达式添加到集合中，这个时候需要注意的是负数、多位数的处理。2.将中缀表达式转换成后缀表达式，并入栈。3.将保存后缀表达式的栈进行弹出并计算，遍历集合，遇到数字直接入新的栈，如果是符号，弹出栈顶两个元素进行计算并入栈。4.最后新的栈中剩下的一个数则为最后的结果。
三、代码实现
public class HJ54Demo {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
//将输入的中缀表达式转换成集合
List<String> paramList = expressionToList(s);
//中缀转后缀
List<String> strings = parseSuffixExpressionList(paramList);
//计算后缀
Integer calculate = calculate(strings);
//输出结果
System.out.println(calculate);
}
private static Integer calculate(List<String> strings) {
Stack<Integer> result = new Stack();
for (String s : strings) {
//如果是数字
if (s.matches("^(\\-|\\ )?\\d (\\.\\d )?$")) {
result.push(Integer.valueOf(s));
} else {
Integer num2 = result.pop();
Integer num1 = result.pop();
int operator = operator(num1, num2, s);
result.push(operator);
}
}
return result.pop();
}
//中缀转后缀
public static List<String> parseSuffixExpressionList(List<String> paramList) {
//符号栈
Stack<String> s1 = new Stack();
//存储中间结果
List<String> s2 = new ArrayList<>();
for (String param : paramList) {
//1.如果是数 直接加入到s2
if (param.matches("^(\\-|\\ )?\\d (\\.\\d )?$")) {
s2.add(param);
} else if ("(".equals(param)) {
//2.如果是（ 直接加入符号栈
s1.push(param);
} else if (")".equals(param)) {
//3.如果是( 依次弹出s1栈顶符号 压入s2 直到遇到左括号 然后将)弹出
while (!s1.peek().equals("(")) {
s2.add(s1.pop());
}
//弹出 )
s1.pop();
} else {
//4.其他情况
//如果当前符号优先级小于等于符号栈顶符号
while (s1.size() != 0 && getPriority(s1.peek()) >= getPriority(param)) {
s2.add(s1.pop());
}
s1.push(param);
}
}
//将符号栈剩余的添加到s2
while (s1.size() != 0) {
s2.add(s1.pop());
}
return s2;
}
//将中缀表达式转换成集合
private static List<String> expressionToList(String s) {
List<String> list = new ArrayList<>();
//多位数拼接
String str = "";
for (int i = 0; i < s.length(); i ) {
char c = s.charAt(i);
//是数字
if (c >= 48 && c <= 57) {
str = c;
if (i == s.length() - 1) {
list.add(str);
}
} else {
//表达式第一位就是 - 号
if ((i == 0 && c == '-')) {
str = c;
} else {
if (c == '-') {
char c1 = s.charAt(i - 1);
//如果 - 前面是符号 并且不是右括号 则进行拼接
if ((c1 < 48 || c1 > 57) && c1 != ')') {
str = c;
} else {
//直接添加到集合中
list.add(str);
list.add(String.valueOf(c));
str = "";
}
} else {
//非数字
list.add(str);
list.add(String.valueOf(c));
str = "";
}
}
}
}
//这里会拼接上空字符串，索性进行一个去空字符串
return list.stream().filter(ss -> !"".equals(ss)).collect(Collectors.toList());
}
//根据不同的符号执行不同的操作
private static int operator(int num1, int num2, String op) {
int result = 0;
switch (op) {
case " ":
result = num1 num2;
break;
case "-":
result = num1 - num2;
break;
case "*":
result = num1 * num2;
break;
case "/":
result = num1 / num2;
break;
}
return result;
}
//判断符号优先级
public static int getPriority(String op) {
if ("*".equals(op) || "/".equals(op)) {
return 2;
} else if (" ".equals(op) || "-".equals(op)) {
return 1;
} else {
return -1;
}
}
}
是一个先入后出的有序列表。栈是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表，允许插入和删除的一端，为变化的一端，称为栈顶，另一端为固定的一端，称为栈底。根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。
前缀表达式又称为波兰式，运算符位于操作数之前例如：（3 4）* 5 -6 前缀表达式是 - X 3 4 5 6
前缀表达式计算：从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的运算，并将结果压入栈。重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果。
中缀表达式就是常见的运算表达式，例如 （3 4）* 5 -6
后缀表达式（逆波兰表达式）与前缀表达式相似，只是运算符位于操作数之后例如：（3 4）X 5 -6 后缀表达式 3 4 5 X 6 -
后缀表达式计算：从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶两个数，用运算符对它们做相应的运算，并将结果压入栈，重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果。
中缀表达式转后缀表达式思想
- 初始化两个栈，运算符栈s1和储存中间结果的栈s2；
- 从左至右扫描中缀表达式；
- 遇到操作数时，将其压s2；
- 遇到运算符时，比较其与s1栈顶运算符的优先级；- 如果s1为空，或栈顶运算符为左括号“（”，则直接将此运算符入栈；- 否则，若优先级比栈顶运算符的高，也将运算符压入s1；- 否则，将s1栈顶的运算符弹出并压入到s2中，再次转到4.a与s1中新的栈顶运算符相比较；
- 遇到括号时：- 如果是左括号“（”，则直接压入s1- 如果是右括号“）”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃。
- 重复步骤2-5，直到表达式的最右边；
- 将s1中剩余的运算符依次弹出并压入s2；
- 依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式。
