1,三种表达式
1)三种表达式
image.png
四则运算的三种表达方式,用于四则运算表达式求值
中缀表达式:(3+4)*5-6
后缀表达式(逆波兰表达式
):3 4 + 5 * 6 -
前缀表达式(波兰式
):- * + 3 4 5 6
2)中缀表达式转后缀表达式(运算符位于操作数
)
步骤一:从左至右扫描表达式,遇到操作数直接到输出栈outputLinkedList
步骤二:遇到运算符时
如果operatorLinkedList
为空,则直接入栈
如果(
,直接入栈
遇到)
,则将(...)
直接操作符依次pop并输出到outputLinkedList
,并丢弃(
步骤三:与栈顶运算符比较优先级,高于栈顶元素则直接入栈。
低于或者同级,则从栈顶开始,依次pop高于或者同级的运算符,输出到outputLinkedList
3)前缀表达式
从右向左扫描表达式。
4)使用后缀表达式计算
步骤一:新建一个栈
步骤二:从左到右扫描后缀表达式,遇到数字则直接入栈
步骤三:遇到操作符,则依次弹出Y,X两个元素,计算Xops
Y,并将结果入栈。
步骤四:最后输出栈顶的值。
5)(3+4)*5-6 转成后缀表达式的例子
后缀表达式outputLinkedList
操作符栈operatorLinkedList
无
|(
3
|(+
34
|(+)
---> 34+
34+
|*
34+5*
|-
-的优先级低于*
3 4 + 5 * 6 -
2,Java Demo
package com.hzq.study;
import java.util.Iterator;
import java.util.LinkedList;
/**
* Created on 2018/4/8.
*/
public class Calculator {
public static void main(String[] args) {
//用栈暂存操作符
LinkedList<String> operators = new LinkedList<>();
//后缀表达式
StringBuilder sb = new StringBuilder();
String str = "6 * ( 5 + ( 2 + 3 ) * 8 + 3 )";
String [] array = str.split(" ");
for(String item : array){
if(isOperators(item)){ //处理操作符
if(operators.isEmpty()){//栈为空则直接入栈
operators.push(item);
} else {
//获取栈顶元素的优先级
int stackHeadItemPriority = priority(operators.peek());
//获取读入元素的优先级
int itemPriority = priority(item);
//如果读入元素为")",则弹出"()"之间的元素到后缀表达式
if(")".equals(item)){
while (!"(".equals(operators.peek())){
String operator = operators.pop();
sb.append(operator).append(" ");
}
if("(".equals(operators.peek())){
operators.pop();
}
//如果读入元素优先级大于栈顶元素,则直接入栈 "("优先级定义为最高,则也会直接入栈
} else if(itemPriority > stackHeadItemPriority){
operators.push(item);
//如果读入元素不为")",且优先级低于或者同级操作符,则依次弹出到后缀表达式,直到遇到比自己低的操作符。
} else if(itemPriority <= stackHeadItemPriority){
while (operators.size() != 0 && !operators.peek().equals("(")){
String operator = operators.pop();
sb.append(operator).append(" ");
}
operators.push(item);
}
}
} else {
//处理操作数
sb.append(item).append(" ");
}
}
//最后操作符栈不为空,则一次pop到后缀表达式
if(!operators.isEmpty()){
Iterator<String> iterator = operators.iterator();
while (iterator.hasNext()){
String operator = iterator.next();
sb.append(operator).append(" ");
iterator.remove();
}
}
System.out.println("后缀: " + sb);
System.out.println(calculatorByOperator(sb.toString()));
}
/**
* 判断一个字符串是不是操作符
* @param str
* @return
*/
public static boolean isOperators(String str){
if("+".equalsIgnoreCase(str) || "-".equalsIgnoreCase(str)
|| "*".equalsIgnoreCase(str) || "/".equalsIgnoreCase(str)
|| "(".equalsIgnoreCase(str) || ")".equalsIgnoreCase(str)){
return true;
}
return false;
}
/**
* 返回操作符的优先级
* @param str
* @return
*/
public static int priority(String str){
switch (str){
case "+":
return 1;
case "-":
return 1;
case "*":
return 2;
case "/":
return 2;
case "(":
return 3;
case ")":
return 3;
default:
return 0;
}
}
/**
* 使用操作符计算两个操作数
* @param opsNum1
* @param opsNum2
* @param operator
* @return
*/
public static int calculator(int opsNum1, int opsNum2, String operator){
switch (operator){
case "+":
return opsNum1 + opsNum2;
case "-":
return opsNum1 - opsNum2;
case "*":
return opsNum1 * opsNum2;
case "/":
return opsNum1 / opsNum2;
default:
return 0;
}
}
/**
* 根据后缀表达式计算值
* @param postExpression
* @return
*/
public static int calculatorByOperator(String postExpression){
LinkedList<String> tempResultList=new LinkedList<>();//新建一个栈,来存储临时结果
String[] postArray = postExpression.split(" ");
for(String str : postArray){//扫描后缀表达式
if(isOperators(str)){//操作符则弹出栈顶另个元素,Y, X,使用 X [ops] Y计算
if(!tempResultList.isEmpty()){
int numY = Integer.valueOf(tempResultList.pop());
int numX = Integer.valueOf(tempResultList.pop());
if(str.equals("/") && numY == 0){
System.out.println("除数不能为0");
throw new RuntimeException("除数不能为0");
}
int tempResult = calculator(numX, numY, str);
tempResultList.push(String.valueOf(tempResult));
}
} else {
tempResultList.push(str);//操作数直接入栈
}
}
return Integer.valueOf(tempResultList.pop());
}
}
网友评论