算法基础课第二章(用于自己复习)
作者:
dameng
,
2023-03-08 10:41:10
,
所有人可见
,
阅读 129
y总的模板
自己做的题目
模拟单链表
828. 模拟栈
3302. 表达式求值
import java.util.*;
public class Main{
static Stack<Integer> num = new Stack<>();
static Stack<Character> op = new Stack<>();
static Map<Character, Integer> map = new HashMap<>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
char[] str = sc.nextLine().toCharArray();
map.put('+', 1);
map.put('-', 1);
map.put('*', 2);
map.put('/', 2);
// 此题目的可扩展性体现在这里,还可以加入次方等等,只要在eval里做好定义即可
// map.put('^', 3);
// 遍历表达式时有四种情况
for (int i = 0; i < str.length; i ++ ) {
char c = str[i];
if (Character.isDigit(c)) { // 1. 如果是数字,就提取数字
int j = i;
int x = 0;
while (j < str.length && Character.isDigit(str[j])) x = x * 10 + str[j ++ ] - '0';
num.push(x);
i = j - 1;
} else if (c == '(') { // 2. 是左括号就入栈
op.push(c);
} else if (c == ')') { // 3. 是右括号就把左右括号之间的算完
// 把左右括号之间的计算完
while (!op.isEmpty() && op.peek() != '(') eval();
// 再把左括号弹出
op.pop();
} else { // 4. 其他运算符时,如果待入栈符号优先级小于等于栈顶,那就一直做运算,直到大于后入栈
// 这里对左括号做了额外的判断,主要是因为左括号在map里没有对应的数字,java会报空指针异常
while (!op.isEmpty() && op.peek() != '(' && map.get(c) <= map.get(op.peek())) eval();
op.push(c);
}
}
// 对运算符栈最后的进行计算
while (!op.isEmpty()) eval();
System.out.println(num.peek());
}
public static void eval() {
int b = num.pop();
int a = num.pop();
char ops = op.pop();
int res = 0;
if (ops == '+') res = a + b;
if (ops == '-') res = a - b;
if (ops == '*') res = a * b;
if (ops == '/') res = a / b;
// if (ops == '^') res = a ^ b;
num.push(res);
}
}
154. 滑动窗口