逆波兰表达式实现简单计算器功能
问题概述
使用逆波兰表达式计算结果
创建一个栈S1用于存储数值，从左到右遍历逆波兰表达式（后缀表达式）
取出数为数值压入栈中
取出数为符号时，弹出栈中两个数值进行计算，并将计算结果压入数值栈中。
重复2，3部直至到后缀表达式底部
代码实现简单计算器功能
作者：justLym
我们完成一个逆波兰计算器，要求完成如下任务
输入一个中缀表达式，转成后缀表达式（逆波兰表达式），使用stack计算结果 要求支持小括号，和多位整数，我们暂时不考虑小数问题 逆波兰表达式书写逆波兰表达式（Reverse Polish notation, RPN,或逆波兰记法），也叫后缀表达式，运算符写在数值的后面
为什么要使用逆波兰表达式呢实现逆波兰表达式其实并不是很难，但是为什么要将看似简单的中缀表达式转成后缀表达式呢？
其实中缀表达式只是对人类而言是简单的，然而对于计算机来说，中缀表达式是一个非常复杂的结构。而后缀表达式对于计算机是一个很容易理解的结构。因为计算即执行的是一个栈结构，执行先进后出的顺序
将1 + （（2 + 3）* 4）- 5 转成后缀表达式为1 2 3 + 4 * 5 - +
| 取出的操作数 | S1栈（栈底 --> 栈顶） | S2栈（栈底 --> 栈顶） | 步骤说明 |
|---|---|---|---|
| 1 | 空 | 1 | 将数值1压入数值栈中 |
| + | + | 1 | 符号栈中为空，直接压入符号栈 |
| （ | + （ | 1 | 操作符为（直接压入符号栈中 |
| （ | + （ （ | 1 | 操作符为（ 直接压入符号栈中 |
| 2 | + （ （ | 1 2 | 取出操作数为数值直接压入数值栈中 |
| + | + （ （ + | 1 2 | 符号栈的栈顶为（括号直接压入符号栈中 |
| 3 | + （ （ + | 1 2 3 | 取出操作数为数值直接压入数值栈中 |
| ） | + （ | 1 2 3 + | 取出操作符为）弹出符号栈中的符号直到弹出最近的（，并将弹出的符号压入数值栈中 |
| * | + （ * | 1 2 3 + | 取出操作符为*并且当前操作符级别大于栈顶操作符级别，直接压入符号栈 |
| 4 | + （ * | 1 2 3 + 4 | 取出操作数为数值直接压入数值栈中 |
| ） | + | 1 2 3 + 4 * | 取出操作符为）弹出符号栈中的符号直到弹出最近的（，并将弹出的符号压入数值栈中 |
| - | + - | 1 2 3 + 4 * | 取出操作符为*并且当前操作符级别大于栈顶操作符级别，直接压入符号栈 |
| 5 | + - | 1 2 3 + 4 * 5 | 取出操作数为数值直接压入数值栈中 |
| 空 | 空 | 1 2 3 + 4 * 5 - + | 清空符号栈S1 |
| 取出的数值 | 栈（栈底 – > 栈顶） | 步骤说明 |
|---|---|---|
| 1 | 1 | 操作数为数值压入栈中 |
| 2 | 1 2 | 操作数为数值压入栈中 |
| 3 | 1 2 3 | 操作数为数值压入栈中 |
| + | 1 5 | 操作数为符号，弹出两个数值进行运算，将运算结果压入栈中 |
| 4 | 1 5 4 | 操作数为数值压入栈中 |
| * | 1 20 | 操作数为符号，弹出两个数值进行运算，将运算结果压入栈中 |
| 5 | 1 20 5 | 操作数为数值压入栈中 |
| - | 1 15 | 操作数为符号，弹出两个数值进行运算，将运算结果压入栈中 |
| + | 16 | 操作数为符号，弹出两个数值进行运算，将运算结果压入栈中 |
import java.util.List;
import java.util.ArrayList;
public class Calculator {
public static void main(String[] args) {
String express = "1+((2+3)*4)-5":
List suffixExpression = SuffixExpression.toSuffixExpression(list);
int calculate = SuffixExpression.calculate(suffixExpression);
System.out.println(calculate);
}
/**
* 将一个算式解析成一个个元素
* @param 需要截取的字符串
*/
public static List strToList(String str) {
if (str == null || str.length() <= 0) {
throw new IllegalArgumentException();
}
List list = new ArrayList();
for (int i = 0;i < str.length();i++) {
if (str.charAt() 57) {
list.add("" + str.charAt(i));
} else {
String sub = "":
while (i = 48 && str.charAt(i) <= 57) {
sub += str.charAt(i);
list.add(sub);
i++;
}
}
}
return list;
}
/**
* 将中缀表达式转逆波兰表达式（后缀表达式）
* @param 需要转的中缀表达式
*/
public static List toSuffixExpression(List list) {
if (list == null || list.isEmpty()) {
throw new IllegalArgumentException();
}
// 用于存放操作符的
Stack stack = new Stack();
// 用于存放数值，由于最后我们是需要逆序输出数值栈，所以这里直接用集合替代栈，可以免去逆序打印
List suffix = new ArrayList();
for (String str:list) {
if (str.matches("\\d")) {
suffix.add(str);
} else if (str.equals("(")) {
stack.push(str);
} else if (str.equals(")")) {
while (!stack.peek().equals("(")) {
suffix.add(stack.pop());
}
stack.pop();
} else {
while (stack.size() > 0 && getValue(str) 0){
suffix.add(stack.pop());
}
}
/**
* 根据逆波兰表达式计算结果
* @param 需要计算的逆波兰表达式
*/
public static int calculator(List list) {
if (list == null || list.isEmpty()) {
throw new IllegalArgumentException();
}
Stack stack = new Stack();
for (String str:list) {
if (str.matches("\\d")) {
stack.push(str);
} else {
int num1 = Integer.parseInt(stack.pop());
int num2 = Integer.parseInt(stack.pop());
if (str.equals("+")){
stack.push(String.valueOf(num1+num2));
}else if (str.equals("-")){
stack.push(String.valueOf(num2-num1));
}else if (str.equals("*")){
stack.push(String.valueOf(num1*num2));
}else if (str.equals("/")){
stack.push(String.valueOf(num2/num1));
}
}
}
return Integer.parseInt(stack.pop());
}
/**
* 计算输入字符的优先级
* @param 需要判断的字符
*/
public static int getValue(String str){
int result;
switch (str){
case "+":
result = 1;
break;
case "-":
result = 1;
break;
case "*":
result = 2;
break;
case "/":
result = 2;
break;
default:
result = 0;
break;
}
return result;
}
}
代码写完，小弟只是能力有限，难免有漏洞，欢迎各路大神指点评论！！！
作者：justLym
