# 计算器：中缀表达式转后缀表达式

```package cn.tzy.calculator;

import java.util.HashMap;
import java.util.Map;
import java.util.Queue;
import java.util.Stack;

/**
* Created by gchx on 2015/2/9.
*/
public class Calculator {

private Map<String, Integer> priority;//操作符优先级Map

public Calculator() {
initPriority();
}

private void initPriority() {
this.priority = new HashMap<>();
//这里的#号是操作符堆栈中的栈底元素，是为了程序方便处理而添加的
this.priority.put("#", 0);
this.priority.put("+", 1);
this.priority.put("-", 1);
this.priority.put("*", 2);
this.priority.put("/", 2);
}

//得到操作符的优先级
public int getPriority(String operator) {
//这里括号进行特殊处理
if (operator.matches("[()]")) {
return -1;
} else {
return priority.get(operator);
}
}

//判断优先级高低
private boolean isPrior(String one, String another) {
return getPriority(one) <= getPriority(another);
}

//得到栈顶元素
private <T> T getTopEle(Stack<T> stack) {
if (stack == null) {
return null;
} else {
return stack.get(stack.size() - 1);
}
}

/**
* @param expression 算数表达式
* @return
* 将中缀表达式转换为后缀表达式
*/
public Queue<String> toSuffix(String expression) {
Queue<String> operandQueue = new LinkedList<>();//操作数队列
Stack<String> operatorStack = new Stack<>();//操作符堆栈
operatorStack.push("#");

String current = "";
String operator = "";
String number = "";
int start = 0;
int end = 0;
for (int i = 0; i < expression.length(); i++) {
current = String.valueOf(expression.charAt(i));
// 如果是数字，末尾标记end++
if (current.matches("[\\d\\.]")) {
// 如果数字是最后一个字符，直接将其入队列
if (i == expression.length() - 1) {
} else {
end++;
}
} else {
// 如果是字符
// 如果是左括号，将其入栈
if (current.equals("(")) {
operatorStack.push(current);
} else {
// 如果是右括号和其它运算符，先将前面的数字入队列
number = expression.substring(start, end);
if (!number.isEmpty()) {
}
// 如果是右括号，执行出栈操作，并将出栈的元素入队列，直到弹出栈的是左括号，左括号直接出栈
if (current.equals(")")) {
while (!getTopEle(operatorStack).equals("(")) {
}
operatorStack.pop();
} else {
// 如果是其它运算符，弹出所有优先级大于或者等于该运算符的栈顶元素，然后将该运算符入栈
operator = current;
while (isPrior(operator, getTopEle(operatorStack))) {
}
operatorStack.push(operator);
}
}
// 将指向数字的首尾指针加1
start = end = i + 1;
}
}

for (int i = operatorStack.size() - 1; i > 0; i--) {
}

return operandQueue;
}

/**
* @param expression 算数表达式
* @return
* 得到表达式的结果
*/
public double getResult(String expression) {
Queue<String> suffixQueue = toSuffix(expression);
Stack<String> suffixStack = new Stack<String>();
String current = "";
double frontOperand;
double backOperand;
double value = 0;
for (int i = suffixQueue.size(); i > 0; i--) {
current = suffixQueue.poll();
//如果是数字，入栈
if (current.matches("^\\d+(\\.\\d+)*\$")) {
suffixStack.push(current);
} else {
backOperand = Double.valueOf(suffixStack.pop());
frontOperand = Double.valueOf(suffixStack.pop());
if (current.equals("+")) {
value = frontOperand + backOperand;
} else if (current.equals("-")) {
value = frontOperand - backOperand;
} else if (current.equals("*")) {
value = frontOperand * backOperand;
} else if (current.equals("/")) {
try {
value = frontOperand / backOperand;
} catch (Exception e) {
return 0;
}
}
suffixStack.push(String.valueOf(value));
}
}
String result = suffixStack.get(0);
return Double.valueOf(result);
}

}```

```package cn.tzy.calculator;

import java.util.Queue;

import org.junit.Assert;
import org.junit.Test;

public class CalculatorTest {

private Calculator calculator;
private String infix;

public CalculatorTest() {
this.calculator = new Calculator();
this.infix = "(8+9*10)-4/2+3";
}

@Test
public void testToSuffix() {
Queue<String> suffix = calculator.toSuffix(infix);
for (int i = suffix.size(); i > 0; i--) {
System.out.print("(" + suffix.poll() + ")");
}
}

@Test
public void testGetResult() {
double result = calculator.getResult(infix);
Assert.assertEquals(result, 99, 0);
}
}```

0 条评论

• ### C++函数指针和std::function对象

这篇博文中通过实现对String字符串大小写转换为列来说明C++中函数指针和std::function对象的使用。

• ### 时期和ANSI Date之间的转换

一个具体日期的ANSI Date指的是该日期到1600年12月31日经过的天数。 1601年1月1日的ANSI Date为1。 在Linux中使用如下命...

• ### macOS下安装ENVI

然后安装依赖的软件： 1. Java6 下载 - Java for OS X 2015-001 2. XQuartz https://www.xquar...

• ### Mac下golang实现Java加密方式调用

安装完毕会在home目录下usr/local/go默认的安装目录。然后这个时候可以配置下环境变量

• ### application.yml与bootstrap.yml的区别

Spring Cloud 构建于 Spring Boot 之上，在 Spring Boot 中有两种上下文，一种是 bootstrap，另外一种是 applic...

• ### base64编码在silverlight中的使用

在传统的.net应用中，使用base64编码字符串是一件很轻松的事情，比如下面这段代码演示了如何将本地文件转化为base64字符串，并且将base64字符串又还...

• ### 听说：微软允许用户自行制作逼格超高的AR版PPT？

信息化时代的当下，人与人之间的沟通讲究直接与高效，对于追求效益的企业来说更是如此。如何让客户快速了解公司及相关产品，那么你可能需要一份视觉美观、逻辑清晰的PPT...

• ### 迁移中的企业科技新范式｜商业洞见

[摘要] 科技现在已经成为商业变革必不可少的推动力量，引领着我们从数字时代进入后数字时代。演进中的交互、增强人类效能、平台的兴起、安全和机器人的崛起这五个宏观板...

• ### IDEA 公司真牛逼，发行适合程序员编程字体

JetBrains今天推出了一种新字体，即JetBrains Mono，它是专为开发人员设计的。

• ### 一个IT人眼里的“云丰杯”全国逆向物流设计大赛

6月底的上海，空气粘湿，闷热异常，用古龙的话来说就是"空气像是牛肉汤上凝固的油脂"。而比天气更热烈的，则是在上海大学举办的第二届全国逆向物流设计大赛。