中缀表达式转后缀表达式
程序员文章站
2022-09-27 13:40:55
先声明负数,小数处理会出错！ 需要使用栈的知识，直接用数组去模拟比较容易看懂所以我就来模拟一下了。 先来了解一下原理： 1、运算数：直接输出 2、左括号：压入堆栈 3、右括号：将栈顶的运算符弹出并输出，直到遇到左括号。 4、运算符： 若优先级大于栈顶运算符，则把它压栈。 若优先级小于等于栈顶运算符， ......
根据中缀表达式求逆波兰表达式（思路清晰）
具体步骤
- 初始化两个栈，一个临时栈tempStack，一个操作符栈operaStack
- 从左至右扫描中缀表达式
- 遇到操作数直接入tempStack
- 遇到操作符时（不包括括号）
4.1 若operaStack为空或者栈顶为’(’，则直接入operaStack
4.2 若operaStack不为空且栈顶元素不为’(’，比较栈顶操作符和当前操作符优先级，若比栈顶优先级高，直接压入operaStack（乘除优先级大于加减）
4.3 否则取出operaStack栈顶操作符并压入tempStack栈，接着回到4.1步骤与新的栈顶元素进行比较 - 遇到括号时
5.1 如果是左括号’(’，压入operaStack
5.2 如果是右括号’)’，则依次弹出operaStack操作符并压入tempStack，直到遇到左括号为止。丢弃左右括号 - 重复2到5步骤，直到表达式最右边
- 将operaStack剩余的元素依次弹出并压入tempStack
- 依次弹出tempStack，逆序之后为后缀表达式，即逆波兰表达式
代码实现
package com.twilight.algorithm.calculator;
import java.util.Stack;
public class ExpressConvert {
public static void main(String[] args) {
System.out.println(infixToSuffix("1+((2+3)*4)-5")); // 123+4*+5-
}
public static String infixToSuffix(String s) {
// 1. 初始化两个栈，一个临时栈tempStack，一个操作符栈operaStack
Stack<Character> operaStack = new Stack<>();
Stack<Character> tempStack = new Stack<>();
// 2. 从左至右扫描中缀表达式
for(int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
int cLevel = CharLevel.level(c);
// 3. 遇到操作数直接入tempStack
if(cLevel == 0) {
tempStack.push(c);
} else if(cLevel == 4) {
// 5. 遇到括号时
// 5.1 如果是左括号'('，压入operaStack
operaStack.push(c);
} else if(cLevel == 1) {
// 5.2 如果是右括号')'
while(true) {
// 5.2 则依次弹出operaStack操作符并压入tempStack，直到遇到左括号位置。丢弃左右括号
char cc = operaStack.pop();
if(CharLevel.level(cc) == 4) {
break;
}
tempStack.push(cc);
}
} else {
// 4. 遇到操作符时（不包括括号）
while(true) {
// 4.1 若operaStack为空或者栈顶为'('，则直接入operaStack
if(operaStack.isEmpty() || operaStack.peek() == '(') {
operaStack.push(c);
break;
}
char cc = operaStack.peek();
int ccLevel = CharLevel.level(cc);
// 4.2 比较栈顶操作符和当前操作符优先级，若比栈顶优先级高，直接入operaStack
if(cLevel > ccLevel) {
operaStack.push(c);
break;
} else {
// 4.3 否则取出operaStack栈顶操作符并压入tempStack栈，接着回到4.1步骤
tempStack.push(operaStack.pop());
}
}
}
// 6. 重复2到5步骤，直到表达式最右边
}
while(!operaStack.isEmpty()) {
// 7. 将operaStack剩余的元素依次弹出并压入tempStack
tempStack.push(operaStack.pop());
}
StringBuilder sb = new StringBuilder();
// 8. 依次弹出tempStack，逆序之后即为逆波兰表达式，即后缀表达式
while(!tempStack.isEmpty()) {
sb.append(tempStack.pop());
}
return sb.reverse().toString();
}
}
package com.twilight.algorithm.calculator;
public class CharLevel {
public static int level(char c) {
if("(".indexOf(c) > -1) {
return 4;
} else if("*/".indexOf(c) > -1) {
return 3;
} else if("+-".indexOf(c) > -1) {
return 2;
} else if(")".indexOf(c) > -1) {
return 1;
} else {
// 数字
return 0;
}
}
}
本文地址：https://blog.csdn.net/XlxfyzsFdblj/article/details/107487089