当前位置：网站首页>计算器：中缀表达式转后缀表达式
计算器：中缀表达式转后缀表达式
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.
边栏推荐
猜你喜欢
关于Request复用的那点破事儿。研究明白了，给你汇报一下。
win10系统重装，无法登录进行同步的情况下chrome数据恢复
如何使用 Authing 单点登录，集成 Discourse 论坛？
2022 Go生态圈 rpc 框架 Benchmark
Find objects with the same property value Cumulative number Summarize
音视频技术开发周刊 | 256
The CAN communication standard frame and extended frame is introduced
《MySQL核心知识》第6章：查询语句
Pytest e-commerce project combat (below)
故障007：dexp导数莫名中断
随机推荐
大中型网站列表页翻页过多怎么优化?
The use of Ts - Map type
leetcode/submatrix element sum
How to use DevExpress controls to draw flowcharts?After reading this article, you will understand!
Qt获取文件夹下所有文件
Grafana9.0发布，Prometheus和Loki查询生成器、全新导航、热图面板等新功能！
SCHEMA solves the puzzle
找出相同属性值的对象 累加数量 汇总
CAN通信的数据帧和远程帧
2022 Go生态圈 rpc 框架 Benchmark
【面试高频题】难度 1.5/5，二分经典运用题
LeetCode_动态规划_中等_377.组合总和 Ⅳ
易周金融分析 | 银行ATM机智能化改造提速；互联网贷款新规带来挑战
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
Data frame and remote frame of CAN communication
STM32 CAN过滤器配置详解
Simulation implementation of new of Js handwritten function
数据湖 delta lake和spark版本对应关系
Transfer learning to freeze the network:
Tencent Cloud Native: Service Mesh Practice of Areaki Mesh in the 2022 Winter Olympics Video Live Application