详细的注释，哪里有问题评论区指出
package com.zy.demo;
import java.sql.Connection;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Stack;
/**
* Copyright:www.zhaoyang.wicp.vip
* Author:王昭阳 -小明机器人
* Date:2021/10/12
* Description:代码版权声明 实现逆波兰计算器
* 代码思路
* 先将表达式转换为逆波兰表达式 步骤如下
* 1.如果遇到‘（’ 直接入S1
* 2.如果遇到数字直接压入S2
* 3.如果遇到‘）’，将S1栈顶距离最近知道‘（’元素依次弹出并依次压入S2
* 4. 如果遇到符号X ， X的优先级大于S1栈顶，X压入S1，X的优先级小于或等于S1栈顶进行如下操作
* S1弹出栈顶元素，并压入S2,直到X优先级大于S1栈顶元素或者该元素为‘（’，再将X压入S1
* 5.遍历结束之后看S1是否为空，若不为空，依次将S1元素弹出并压入S2
*
*
*
* 逆波兰表达式计算结果代码思路如下
*
* 从左到右依次遍历 定义一个stack即可
* 如果是数字，直接压栈，
* 如果是符号（不是数字），则出栈两次，第一次出栈定义为b ,第二次出栈a ,然后 a opa b
* 栈中剩下一个元素就是结果
*
*
*/
public class PolandClient {
public static void main(String[] args) {
String cir = "90+(3-1)*3+10/2";
ArrayList<String> list_po = getPolandString(cir);//返回逆波兰表达式
double answer = getAnswer(list_po);
System.out.println(answer);
}
//该字符是否为数字
public static boolean isNum(char x) {
if (x >= '0' && x <= '9') {
return true;
} else return false;
}
//获取符号的优先级
public static int getPor(char opera) {
int por = 0;
if (opera == '+') {
por = 1;
}
if (opera == '-') {
por = 1;
}
if (opera == '*') {
por = 3;
}
if (opera == '/') {
por = 3;
}
if (opera == '#') {
por = 0;
}
return por;
}
public static ArrayList<String> getPolandString(String cirString) {
Stack<String> s1; //定义两个栈 一个符号栈S1 一个操作栈S2
Stack<String> s2;
String cir = cirString;
char[] chars = cir.toCharArray(); //将表达式转换成字节 依次遍历
s1 = new Stack<>();
s2 = new Stack<>();
int index = 0;
while (true) { //进行遍历
int index0 = index;//如果数字大于10,就会用到index0
StringBuilder stringBuilder = new StringBuilder(); // 多次追加数字 用该类比较方便
if (index == cir.length()) { //遍历到满足此条件时候 跳出循环
break;
} else if (isNum(chars[index0])) { //是数字的情况下进行 进行如下操作
stringBuilder.append(chars[index]);//第一个数字追加
index0++;//向后遍历
if (index0 == cir.length()) {
s2.push(stringBuilder.toString());//如果后面到结尾了，入栈并跳出
break;
}
while (isNum(chars[index0])) {//后面那个还是数字进行如下操作
//是数字的话追加
stringBuilder.append(chars[index0]); //追加
index++;//指标后移
index0++;//后移
if (index0 == cir.length()) break;//如果遍历到结尾，跳出循环
}
s2.push(stringBuilder.toString());//将结果入栈
} else if (chars[index] == '(') {//如果遍历到的字符是左括号
stringBuilder.append(chars[index]);//追加
s1.push(stringBuilder.toString());//入栈
} else if (chars[index] == ')') {//如果遍历到的字符是右括号 进行如下操作
while (true) {//将s1元素出栈，并入s2栈,（前提条件是如若s1出栈的符号是左括号,就将左括号出栈，循环结束）（s1为空栈 同样结束循环）
if (!s1.isEmpty()) {//如果s1不是空的
String pop = s1.pop();//出栈 判断
if (pop.equals("(")) {//若它是左括号 循环结束
break;
} else {//否则 入s2栈
s2.push(pop);
}
} else {
break;
}
}
//如下是 遍历到运算符的时候
} else if (chars[index] == '+' || chars[index] == '-' || chars[index] == '*' || chars[index] == '/') {
if (s1.isEmpty() || getPor(chars[index]) > getPor(s1.peek().toCharArray()[0])) {//如果s1为空或者该优先级大于S1栈顶优先级
stringBuilder.append(chars[index]);//追加
s1.push(stringBuilder.toString());//s1入栈
} else if (getPor(chars[index]) <= getPor(s1.peek().toCharArray()[0])) {
//如果该优先级 小于等于s1中优先级，进行如下操作
while (true) {
if (!s1.isEmpty()) {//先判断是否为空
String pop = s1.pop(); //弹出S1栈顶元素
if (pop.equals("(")) {//判断出栈元素是否为左括号 是
s1.push(pop);//将该重新入栈
break;
} else {
s2.push(pop); //否则入S2
}
} else {
break;
}
}
stringBuilder.append(chars[index]);
s1.push(stringBuilder.toString());
}
}
index++;
}
//遍历结束后 对S1判空循环 依次将S1元素弹出并压入S2
while (!s1.isEmpty()) {
String pop = s1.pop();
s2.push(pop);
}
//最后s2依次弹出放S1 ，这样s1出栈的顺序就是原表达式的后缀表示了（逆波兰）
ArrayList<String> list = new ArrayList<>();
while (!s2.isEmpty()) {
list.add(s2.pop());
}
Collections.reverse(list);
System.out.println(Arrays.asList(list));
return list;
}
//ab+cd- 将逆波兰表达式转 计算出结果
public static double getAnswer(ArrayList<String> list) {//参数是 逆波兰栈
Stack<String> s1 = new Stack<>();
for (int i = 0; i < list.size(); i++) {
String pop = list.get(i); //运算栈
if (isNum(pop.toCharArray()[0])) {
s1.push(pop);
} else {
String second = s1.pop();
String first = s1.pop();
double answer = getAnswer(Double.parseDouble(first), Double.parseDouble(second), pop);
s1.push(answer + "");
}
}
if (!s1.isEmpty()) {
String pop = s1.pop();
return Double.parseDouble(pop);
} else {
return 0;
}
}
public static double getAnswer(double a, double b, String c) {
double answer = 0;
if (c.equals("+")) {
answer = a + b;
} else if (c.equals("-")) {
answer = a - b;
} else if (c.equals("*")) {
answer = a * b;
} else if (c.equals("/")) {
answer = a / b;
}
return answer;
}
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。
