当前位置：网站首页>计算器：中缀表达式转后缀表达式
计算器：中缀表达式转后缀表达式
2022-08-01 12:43:00 【51CTO】
这几天想写一个Android的计算器，所以先写好中缀表达式到后缀表达式的计算。
例如：中缀表达式(8+9*10)-4/2+3
我们可以进行如下操作：
1、将每个操作符对应的两个操作数用括号括上(((8+(9*10))-(4/2))+3)
2、将操作符移到对应的括号外(((8(910*)+)(42)/)-3)+
3、去掉括号即可 8910*+42/-3+
是不是很简单，这样我们就讲一个中缀表达式转换成论文后缀表达式。
那么计算机中是怎样进行的呢？
转换的整体流程如下：
中缀表达式转后缀表达式的方法：
1.遇到操作数：直接输出(添加到后缀表达式中)
2.栈为空时，遇到运算符，直接入栈
3.遇到左括号：将其入栈
4.遇到右括号：执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，左括号不输出。
5.遇到其他运算符：加减乘除：弹出所有优先级大于或者等于该运算符的栈顶元素，然后将该运算符入栈
6.最终将栈中的元素依次出栈，输出。
下面是我写得一个示例代码：
package
cn.
tzy.
calculator;
import
java.
util.
HashMap;
import
java.
util.
LinkedList;
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) {
operandQueue.
add(
current);
}
else {
end
++;
}
}
else {
// 如果是字符
// 如果是左括号，将其入栈
if (
current.
equals(
"(")) {
operatorStack.
push(
current);
}
else {
// 如果是右括号和其它运算符，先将前面的数字入队列
number
=
expression.
substring(
start,
end);
if (
!
number.
isEmpty()) {
operandQueue.
add(
number);
}
// 如果是右括号，执行出栈操作，并将出栈的元素入队列，直到弹出栈的是左括号，左括号直接出栈
if (
current.
equals(
")")) {
while (
!
getTopEle(
operatorStack).
equals(
"(")) {
operandQueue.
add(
operatorStack.
pop());
}
operatorStack.
pop();
}
else {
// 如果是其它运算符，弹出所有优先级大于或者等于该运算符的栈顶元素，然后将该运算符入栈
operator
=
current;
while (
isPrior(
operator,
getTopEle(
operatorStack))) {
operandQueue.
add(
operatorStack.
pop());
}
operatorStack.
push(
operator);
}
}
// 将指向数字的首尾指针加1
start
=
end
=
i
+
1;
}
}
for (
int
i
=
operatorStack.
size()
-
1;
i
>
0;
i
--) {
operandQueue.
add(
operatorStack.
pop());
}
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);
}
}
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
- 16.
- 17.
- 18.
- 19.
- 20.
- 21.
- 22.
- 23.
- 24.
- 25.
- 26.
- 27.
- 28.
- 29.
- 30.
- 31.
- 32.
- 33.
- 34.
- 35.
- 36.
- 37.
- 38.
- 39.
- 40.
- 41.
- 42.
- 43.
- 44.
- 45.
- 46.
- 47.
- 48.
- 49.
- 50.
- 51.
- 52.
- 53.
- 54.
- 55.
- 56.
- 57.
- 58.
- 59.
- 60.
- 61.
- 62.
- 63.
- 64.
- 65.
- 66.
- 67.
- 68.
- 69.
- 70.
- 71.
- 72.
- 73.
- 74.
- 75.
- 76.
- 77.
- 78.
- 79.
- 80.
- 81.
- 82.
- 83.
- 84.
- 85.
- 86.
- 87.
- 88.
- 89.
- 90.
- 91.
- 92.
- 93.
- 94.
- 95.
- 96.
- 97.
- 98.
- 99.
- 100.
- 101.
- 102.
- 103.
- 104.
- 105.
- 106.
- 107.
- 108.
- 109.
- 110.
- 111.
- 112.
- 113.
- 114.
- 115.
- 116.
- 117.
- 118.
- 119.
- 120.
- 121.
- 122.
- 123.
- 124.
- 125.
- 126.
- 127.
- 128.
- 129.
- 130.
- 131.
- 132.
- 133.
- 134.
- 135.
- 136.
- 137.
- 138.
- 139.
- 140.
- 141.
- 142.
- 143.
- 144.
- 145.
- 146.
- 147.
- 148.
- 149.
- 150.
- 151.
- 152.
- 153.
- 154.
- 155.
- 156.
- 157.
- 158.
单元测试代码如下：
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);
}
}
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
- 16.
- 17.
- 18.
- 19.
- 20.
- 21.
- 22.
- 23.
- 24.
- 25.
- 26.
- 27.
- 28.
- 29.
- 30.
- 31.
边栏推荐
- Detailed explanation of table join
- 如何利用DevExpress控件绘制流程图？看完这篇文章就懂了！
- 【面试高频题】难度 1.5/5，二分经典运用题
- CloudCompare & PCL ICP registration (point to face)
- How do programmers solve online problems gracefully?
- Meshlab & Open3D SOR filtering
- Apex installation error
- 易周金融分析 | 银行ATM机智能化改造提速；互联网贷款新规带来挑战
- Alibaba Cloud Official Redis Development Specification
- Excel表格打印时不打印标记填充颜色
猜你喜欢
Audio and Video Technology Development Weekly | 256
实现集中式身份认证管理的案例
故障007：dexp导数莫名中断
![[Open class preview]: Research and application of super-resolution technology in the field of video image quality enhancement](/img/fc/cd859efa69fa7b45f173de74c04858.png)
[Open class preview]: Research and application of super-resolution technology in the field of video image quality enhancement
Process sibling data into tree data
CAN通信的数据帧和远程帧
并发编程10大坑，你踩过几个？
【StoneDB Class】入门第二课：StoneDB 整体架构解析
阿里云官方 Redis 开发规范
找出相同属性值的对象 累加数量 汇总
随机推荐
实现集中式身份认证管理的案例
Audio and Video Technology Development Weekly | 256
意大利普拉托华社将游行示威 盼解决安全问题
HMS Core音频编辑服务音源分离与空间音频渲染，助力快速进入3D音频的世界
数据湖 delta lake和spark版本对应关系
软件设计师考点汇总(室内设计师个人总结)
leetcode/submatrix element sum
AI目标分割能力，无需绿幕即可实现快速视频抠图
The difference between undefined and null in JS
Towhee 每周模型
Aeraki Mesh became CNCF sandbox project
SCHEMA solves the puzzle
pandas connects to the oracle database and pulls the data in the table into the dataframe, filters all the data from the current time (sysdate) to one hour ago (filters the range data of one hour)
深入解析volatile关键字
《MySQL核心知识》第6章：查询语句
Envoy source code flow chart
这项工作事关中小学生生命安全！五部门作出联合部署
SCHEMA解惑
bat倒计时代码
大中型网站列表页翻页过多怎么优化?