使用java输出一个表达式的逆波兰式串,计算他的值,参与的数字都是个位数
时间: 2024-04-29 13:23:25 浏览: 114
利用逆波兰式求表达式值
5星 · 资源好评率100%
首先,需要了解逆波兰表达式的概念。逆波兰表达式,也叫后缀表达式,是一种不需要括号来标识优先级的数学表达式。它将运算符放在操作数的后面,因此也被称为后缀表示法。
例如,表达式(3+4)*5-6的逆波兰式为 3 4 + 5 * 6 -
计算逆波兰式的值可以使用栈来实现。具体步骤如下:
1. 从左到右扫描逆波兰式串
2. 遇到数字,将其压入栈中
3. 遇到运算符,弹出栈顶的两个数,进行相应的运算,并将结果压入栈中
4. 最终,栈中只剩下一个数,即为逆波兰式的计算结果
下面是一个实现以上步骤的java代码:
```java
import java.util.*;
public class ReversePolishNotation {
public static void main(String[] args) {
String expression = "3+4*5-6";
String rpn = toRPN(expression);
System.out.println(rpn);
int result = calculateRPN(rpn);
System.out.println(result);
}
// 将中缀表达式转换为逆波兰式
public static String toRPN(String expression) {
StringBuilder rpn = new StringBuilder(); // 逆波兰式串
Stack<Character> stack = new Stack<>(); // 运算符栈
for (int i = 0; i < expression.length(); i++) {
char ch = expression.charAt(i);
if (Character.isDigit(ch)) { // 遇到数字,直接加入逆波兰式串
rpn.append(ch);
} else { // 遇到运算符
while (!stack.isEmpty() && getPriority(stack.peek()) >= getPriority(ch)) {
// 如果栈顶运算符优先级大于等于当前运算符,弹出栈顶运算符加入逆波兰式串
rpn.append(stack.pop());
}
stack.push(ch); // 当前运算符入栈
}
}
while (!stack.isEmpty()) { // 将剩余运算符弹出加入逆波兰式串
rpn.append(stack.pop());
}
return rpn.toString();
}
// 计算逆波兰式的值
public static int calculateRPN(String rpn) {
Stack<Integer> stack = new Stack<>(); // 操作数栈
for (int i = 0; i < rpn.length(); i++) {
char ch = rpn.charAt(i);
if (Character.isDigit(ch)) { // 遇到数字,入栈
stack.push(ch - '0'); // 将字符转换为数字
} else { // 遇到运算符,弹出栈顶的两个数,进行相应的运算,并将结果压入栈中
int b = stack.pop();
int a = stack.pop();
switch (ch) {
case '+':
stack.push(a + b);
break;
case '-':
stack.push(a - b);
break;
case '*':
stack.push(a * b);
break;
case '/':
stack.push(a / b);
break;
}
}
}
return stack.pop(); // 栈中只剩下一个数,即为逆波兰式的计算结果
}
// 获取运算符的优先级
public static int getPriority(char ch) {
switch (ch) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
default:
return 0;
}
}
}
```
在上面的代码中,toRPN方法将中缀表达式转换为逆波兰式,calculateRPN方法计算逆波兰式的值,getPriority方法获取运算符的优先级。
对于输入的表达式"3+4*5-6",运行以上代码的输出结果如下:
```
345*+6-
17
```
其中,逆波兰式串为"345*+6-",计算结果为17。
阅读全文