import java.util.ArrayList;
import java.util.List;
public class MyStack<E> {
private List<E> elements = new ArrayList<>();
/**
* 添加元素(入栈)
* @param e
*/
public void push(E e) {
elements.add(e);
}
/**
* 删除栈顶元素(出栈)
* @return
*/
public E pop() {
return elements.remove(elements.size() - 1);
}
/**
* 查看栈顶元素
* @return
*/
public E peek() {
return elements.get(elements.size() - 1);
}
/**
* 判断栈是否为空
* @return
*/
public boolean isEmpty() {
return elements.size() == 0;
}
}
- 题目:检查表达式中的括号是否匹配(表达式中可能有圆括号，方括号，花括号)
- 要点:使用栈的FILO(先进后出)特性
public class Test {
public static boolean CheckBrackets(String expr) {
MyStack<Character> stack = new MyStack<>();
for (int i = 0; i < expr.length(); i++) {
char temp = expr.charAt(i);
if (temp == '(' || temp == '[' || temp == '{') {
stack.push(temp); //遇到左括号，入栈
}
else if(temp == ')' || temp == ']' || temp == '}') {
if (!stack.isEmpty()) { //先判断栈是否为空，如果不为空，则继续进行
char left = stack.pop(); //遇到右括号，出栈
if ((temp == ')' && left != '(') ||
(temp == ']' && left != '[') ||
(temp == '}' && left != '{')) {
return false; //左括号与右括号不匹配
}
}
else {
return false; //遇到右括号，但没有左括号与之匹配
}
}
}
return stack.isEmpty(); //检查所有左括号是否完成匹配
}
public static void main(String[] args) {
System.out.println(CheckBrackets("([3 + 5] * 2) + (1 * 2)"));
}
}
- 1.需要先将表达式转为逆波兰表达式
- 2.通过转为的逆波兰表达式进行运算
package com.qfedu.day01;
class Q002 {
// 逆波兰表达式 - 中缀表达式转逆波兰表达式
public static double eval(String suffix) { //参数为逆波兰表达式
MyStack<Double> stack = new MyStack<>();
StringBuilder tempStr = new StringBuilder();
for (int i = 0, len = suffix.length(); i < len; ++i) {
char temp = suffix.charAt(i);
if (temp == ' ') {
if (tempStr.length() > 0) {
double num = Double.parseDouble(tempStr.toString());
stack.push(num);
tempStr.delete(0, tempStr.length());
}
}
else if (temp >= '0' && temp <= '9') {
tempStr.append(temp);
}
else {
if (stack.size() >= 2) {
double num2 = stack.pop();
double num1 = stack.pop();
double result = 0;
switch (temp) {
case '+':
result = num1 + num2;
break;
case '-':
result = num1 - num2;
break;
case '*':
result = num1 * num2;
break;
case '/':
result = num1 / num2;
break;
}
stack.push(result);
}
}
}
return stack.pop();
}
public static String toSuffix(String expr) { //转为逆波兰表达式
MyStack<Character> stack = new MyStack<>();
StringBuilder suffix = new StringBuilder();
StringBuilder tempStr = new StringBuilder();
for (int i = 0, len = expr.length(); i < len; ++i) {
char temp = expr.charAt(i);
if (temp != ' ') {
if (temp >= '0' && temp <= '9') {
tempStr.append(temp);
}
else {
if (tempStr.length() > 0) {
suffix.append(tempStr.toString() + " ");
}
tempStr.delete(0, tempStr.length());
if (temp == ')' || temp == ']' || temp == '}') {
Character op = stack.pop();
while (op != '(' && op != '[' && op != '{') {
suffix.append(op + " ");
if (!stack.isEmpty()) {
op = stack.pop();
}
else {
break;
}
}
}
else {
if (temp != '(' && temp != '[' && temp != '{') {
if (!stack.isEmpty()) {
Character op = stack.peek();
while (!hasLowerOrder(op, temp)) {
suffix.append(stack.pop() + " ");
if (!stack.isEmpty()) {
op = stack.peek();
}
else {
break;
}
}
}
}
stack.push(temp);
}
}
}
}
if (tempStr.length() > 0) {
suffix.append(tempStr.toString() + " ");
}
while (!stack.isEmpty()) {
suffix.append(stack.pop() + " ");
}
return suffix.toString();
}
private static boolean hasLowerOrder(char op1, char op2) {
return (op1 == '(' || op1 == '[' || op1 == '{') || ((op1 == '+' || op1 == '-') && (op2 == '*' || op2 == '/'));
}
// 栈(stack) - 线性结构 - FILO
// 队列(queue) - 线性结构 - FIFO
// 堆(heap) - 层次结构 - 完全二叉树
public static void main(String[] args) throws Exception {
System.out.println(eval(toSuffix("2 + 3 * 5")));
System.out.println(eval(toSuffix("(1 + 2 + 3) * 5")));
System.out.println(eval(toSuffix("(1 + 2) * 5 * (2 + 3)")));
System.out.println(eval(toSuffix("(1 + 2) * (5 - 2) * 3)")));
System.out.println(eval(toSuffix("(1 + 2) / (5 * (2 + 3))")));
System.out.println(eval(toSuffix("{[1 + 12 + 234]} * 3456 * (45678 - 567890)")));
}
}
