当前位置：网站首页>计算器：中缀表达式转后缀表达式
计算器：中缀表达式转后缀表达式
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.
边栏推荐
- Simulation implementation of new of Js handwritten function
- Beyond Compare 4 trial period expires
- Envoy source code flow chart
- How to successfully pass the CKA exam?
- 【讲座分享】“营收“看金融
- 华盛顿大学、Allen AI 等联合 | RealTime QA: What's the Answer Right Now?(实时 QA：现在的答案是什么？)
- STM32 CAN过滤器配置详解
- [Unity3D Plugin] AVPro Video Plugin Share "Video Player Plugin"
- 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)
- How to get the address of WeChat video account (link address of WeChat public account)
猜你喜欢
数据湖 delta lake和spark版本对应关系
关于Request复用的那点破事儿。研究明白了，给你汇报一下。
Process sibling data into tree data
bpmn-process-designer基础上进行自定义样式（工具、元素、菜单）
程序员如何优雅地解决线上问题？
2022 Go生态圈 rpc 框架 Benchmark
深入解析volatile关键字
![[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
安装apex报错
安全又省钱，“15岁”老小区用上管道燃气
随机推荐
The CAN communication standard frame and extended frame is introduced
Software designer test center summary (interior designer personal summary)
如何设计一个分布式 ID 发号器？
Favorites|Mechanical Engineer Interview Frequently Asked Questions
Envoy source code flow chart
Aeraki Mesh Joins CNCF Cloud Native Panorama
硬链接、软连接浅析
Deep understanding of Istio - advanced practice of cloud native service mesh
找出相同属性值的对象 累加数量 汇总
R语言两个时间序列数据的滞后相关性可视化：使用forecast包的ccf函数绘制交叉相关函数，根据可视化结果分析滞后相关性
小程序插件如何帮助开发者受益？
A new generation of ultra-safe cellular batteries, Sihao Airun goes on sale starting at 139,900 yuan
程序员的自我修养
蔚来又一新品牌披露：产品价格低于20万
【云享新鲜】社区周刊·Vol.73- DTSE Tech Talk：1小时深度解读SaaS应用系统设计
How to use DevExpress controls to draw flowcharts?After reading this article, you will understand!
程序员如何优雅地解决线上问题？
R language ggplot2 visualization: use ggpubr package ggscatter function visualization scatterplot, use xscale wasn't entirely specified X axis measurement adjustment function, set the X coordinate for
HMS Core音频编辑服务音源分离与空间音频渲染，助力快速进入3D音频的世界
markdown常用数学符号cov(markdown求和符号)