import java.util.Iterator;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Stack;
public class 中缀转后缀demo3 {
static Stack<String> s1 = new Stack<>(); // 装操作符
static Stack<String> s2 = new Stack<>(); // 装数字和那些从s1中弹出来的操作符
static Stack<String> s3 = new Stack<>(); // 装逆序之后的元素,用于计算栈里的值
static Stack<String> s4 = new Stack<>(); // 储存计算的中间结果,即是从s3中出栈,然后压入s4中,遇到操作符,就弹出两个元素,计算完再压入s4栈
static LinkedList<String> list = new LinkedList<>(); //用于储存输入的字符(中缀表达式)
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s;
while (!(s = scanner.next()).equals("#")) {//当输入的值不是#时,继续扫描用户的输入,直到用户输入#,就结束扫描
list.add(s);//没扫描到一个字符,就加入到list链表中
}
bianliList(list);//自定义的一个方法,此方法用于遍历list列表中的元素
transferToHouZhui(list);//此方法用于把输入的中缀表达式输出为后缀表达式,是输出后缀表达式,此方法只是用了遍历,并没有实现return 一个 栈或者链表
total(s3); //此方法用于计算栈内的运算,然后输出计算结果
}
/**
* 此方法将中缀表达式转化为前缀表达式,将装着中缀表达式的list 转为 前缀表达式 s2,s2就装着前缀表达式
* 只不过里面调用了一个becomeNiXu(String s2) 方法,将元素逆序存入到一个数组里面,再遍历出来,就变成了后缀表达式
* @param list
*/
private static void transferToHouZhui(LinkedList<String> list) {//参数为linkedList类型,将list里的元素遍历出来,存入字符栈s1或者输入栈s2
Iterator<String> it = list.iterator();//list类型的遍历要用到迭代器
while (it.hasNext()) {//当迭代器中还有下一个元素时,就继续循环
String s = it.next();//将迭代的元素赋值给一个String类型的变量
if (isOperator(s)) {//如果s是操作符的话,开始判断压入栈的规则,isOperator是一个自定义的方法,用于判断字符是否操作符
if (s1.isEmpty()) {//1.1 首先判断s1里面是否有元素,如果没有元素,则不管s的优先级高或者低都要存进s1栈
s1.push(s);
} else {//1.2 当s1中有元素,则要开始和栈中的元素做比较,比较s优先级是否大于栈顶的元素,当大于时要怎么操作,当小于时要怎么操作
if (level3(s1.peek()) <= level3(s) && !s.equals(")")) {//1.3 如果读入的操作符为非")",并且读入的操作符优先级比栈顶元素的优先级高或者一样,则将操作符压入s1栈
s1.push(s);
} else if (!s.equals(")") && level3(s1.peek()) > level3(s))
{
//1.4 如果读入的操作符为非")",并且优先级比栈顶元素的优先级低,则要开始while循环,这样才可以把栈顶那些优先级比读入的操作符优先级高都弹出来压入到s2栈中
//1.5 在while循环中有点特殊的是在while循环中的比较要加等于号,因为当栈顶的元素优先级等于读入的操作符时,这个时候,因为这个操作符已经在栈内里了,所以它的优先级是比还没存入
// 的操作符优先级要高,这个时候就要弹出去,再压入s2中,举个例子,但栈内有个+号,读入的操作符为-号,虽然说优先级都是1,相等,但是我们要把+弹走,因为她本来就在里面了,优先级默认
// 比还没存入的优先级高,如果在while条件中不加等号的话,当判断到 两个优先级一样的情况下,是不会弹出压入到s2中,这样的话转后缀式就发生错误了
// 1.6 并且在while循环中,我们还要注意装曹操作符的s1栈是否已经全部弹出去了,所以我们要判断s1是否为空
// 1.7 在判断中,如果我们栈顶的元素为"(",这个时候"("优先级为3,读入的操作符优先级如果比"("小,但也不能把"("弹出去,这是个特殊的地方
// 所以在这里的while循环中要判断在s1栈中弹出来的操作符不为"("
while (s1.size() != 0 && level3(s1.peek()) >= level3(s) && !s1.peek().equals("(")) {
String string = s1.pop(); //从s1中弹出栈顶元素,装在string对象中
s2.push(string); //把string压入到s2栈中
}
s1.push(s); //当s都不符合上面的条件后,while循环结束了,代码就可以读到这一行了,就将读入的s压入s1中,
} else if (s.equals(")"))
{
//这里是判断另一个特殊情况,如果读入的操作符为")"的话,就要将栈顶开始往下,将第一个"("前的所有操作符弹出去压入到s2中
while (!s1.peek().equals("(")) {
String string = s1.pop();
s2.push(string);
}
//当栈顶是"("时,就跳出了while循环,这个时候不把")"存入s1中,反而将"("弹出去,不要了
s1.pop();
}
}
} else { //这是判断接着这个方法中的第一个if后面的else,判断读入的s是不是操作符,是就执行if中的语句,不是,就直接将那些数字压入到s2中
s2.push(s);
}
}
while (!s1.isEmpty()) { //当上面的数字全都压入了s2栈中时,可能给s1栈中还有一些操作符还没有弹出来,所以我们就要判断一下s1中是否为空,如果不为空,证明里面还有操作符
//将操作符都弹出来压进s2中
String string = s1.pop();
s2.push(string);
}
becomeNiXu(s2);//自定义的方法,将s2栈中的元素逆序,再输出
}
private static boolean isOperator(String s) //此方法用于判断s是否为操作符
{
if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/") || s.equals("(") || s.equals(")"))
return true;
return false;
}
private static int level3(String oper) //此方法用于给操作符分优先级
{
switch (oper) {
case "+":
return 1;
case "-":
return 1;
case "*":
return 2;
case "/":
return 2;
case "(":
return 3;
case ")":
return 3;
default:
return 0;
}
}
private static void becomeNiXu(Stack<String> s2) //此方法用于将栈中的元素逆序,再输出
{
String[] array = new String[s2.size()]; //new一个新的array数组,数组大小就是s2的大小
int num = 0; //初始化一个指针,用于下面存元素进数组的指针
while (!s2.isEmpty()) { //当s2不为空时,证明还有元素,就继续循环
array[num] = s2.pop(); //s2从栈顶往栈底出栈的时候,就是一个前缀表达式,所以将s2弹出来的栈顶元素存入array数组中,从0角标开始存
//在下面再new一个新的newArray数组来逆序存放这些元素,以此来变成后缀表达式
num++; //角标自增
}
System.out.print("压入s2里的所有元素的遍历: ");
for (String results : array) { //用于遍历array数组,来验证s2是不是前缀表达式,答案是确定的
System.out.print(results);
s3.push(results); //在遍历的同时,将前缀表达式的每一个元素都压入到一个s3栈中,这个时候栈内的排序就是后缀表达式了
}
System.out.println();
/**不能用这个方法,因为这个方法会把s3中的元素都弹走,虽然说是可以输出后缀表达式,但是s3栈是要和s4栈搭配使用来计算表达式的结果
* System.out.print("中缀转后缀之后的表达式: ");
while(!s3.isEmpty())
{
System.out.print(s3.pop());
}
*/
String[] newArray = new String[array.length]; //创建一个newArray数组,来将前缀表达式逆序存入,存入之后再遍历就是后缀表达式了
int index = 0;
for (int i = array.length - 1; i >= 0; i--) {
newArray[index] = array[i];
index++;
}
System.out.print("中缀转后缀之后的表达式: "); //遍历newArray数组,输出后缀表达式
for (String results : newArray) {
System.out.print(results);
}
}
private static void bianliList(LinkedList<String> list) // 遍历list里面的元素
{
Iterator<String> it = list.iterator();
String string;
System.out.print("list里的元素");
while (it.hasNext()) {
string = it.next();
System.out.print(string + " ");
}
System.out.println();
}
// 计算栈内所有元素的值
private static void total(Stack<String> s3) {
while (!s3.empty()) { //当s3不为空的时候,就弹出元素,再判断这个元素是不是操作符,是操作符的话,就弹出s4中的两个栈顶元素来运算,不是操作符的话就压入到s4栈中
String s = s3.pop();
if (isOperator(s)) {
int num1 = Integer.valueOf(s4.pop()); //将String类型转化为int类型
int num2 = Integer.valueOf(s4.pop());
String newNumber = String.valueOf(cal(num2, num1, s));
s4.push(newNumber); //将计算结果再次压入s4栈中
} else {
// 当s3的栈顶不是操作符是,把数字压入s4栈,s4栈用于储存计算中间数
s4.push(s);
}
}
if (!s4.isEmpty()) //计算完后,一般情况下,装结果的s4栈是还剩下一个结果元素的,这个时候我们就要把这个结果输出来
{
System.out.println();
System.out.println("栈内所有元素的算术结果是:" + s4.peek());
}
}
// 计算两个元素的值并返回
private static int cal(int num2, int num1, String operator) {
switch (operator) {
case "+":
return num2 + num1;
case "-":
return num2 - num1;
case "*":
return num2 * num1;
case "/":
return num2 / num1;
default:
return 0;
}
}
}
14.中缀表达式转后缀表达式
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
