中缀表达式就是我们所熟悉的数学算式。如:3 + 6 - 18 / 2或3 + 3 * ( 26 - 16 / 2 ) / 2 + 2 - 20。
我们的目标是要实现一个计算器,来根据中缀表达式计算表达式的值。表达式由数字和+ - * / ()组成。使用两个栈来实现,一个数值栈,一个符号栈。

在这里我们假设表达式都是正确的,并且数值与符号之间由空格隔开。在代码中不再判断表达式的格式是否正确。

<>实现思路

首先要确定的是,运算符是有优先级的。先来考虑没有括号的情况。
我们约定+ -运算符的优先级为1,* /运算符的优先级为2,

<>无括号情况

在没有括号时,我们只需要先计算优先级高的式子,再回过头来计算优先级低的式子即可。入下图所示

流程如下:

* 先分割表达式
* 依次遍历表达式
* 如果是运算符,直接入栈
* 如果是数字,先判断数值栈是否为空,如果为空,则直接入栈;若数值栈不为空,查看符号栈栈顶的符号的优先级,如果是2(* /
),则取出数值栈栈顶元素和符号栈栈顶元素然后进行计算,并将计算结果重新入数值栈,如果优先级是1(+ -)则直接入栈。
* 遍历结束后,符号栈中就只剩下了+ -。
* 遍历符号栈,从栈顶取出运算符,然后从数值栈中取出两个数值,然后进行运算,并将运算结果重新入栈。重复此操作,直到符号栈为空。
<>有括号的情况

有括号的情况会比无括号的情况复杂一些,我们需要将括号内的表达式看成一个完整的子表达式。遇到前括号就算是一个分界点,括号内的运算依然遵循优先级高的先运算的原则,只是不再等待最后计算优先级低的运算。而是遇到后括号后就要开始符号栈的自顶而下的遍历。只到遇到前括号遍历结束。

遍历结束后还不能继续做表达式的遍历,而是应该查看符号栈栈顶的符号优先级是否为2。如果为2,则取出栈顶运算符,再从数值栈中取两个数值,然后进行运算,并将运算结果重新入数值栈。

重复以上步骤,直到符号栈栈顶运算符优先级为1或栈顶符号为(。

<>代码实现
package com.codestd.study.stack; import org.apache.commons.lang3.StringUtils;
import java.util.Stack; /** * 中缀表达式 * * @author jaune * @since 1.0.0 */ public
class InfixExpression { /** * 计算表达式的值 * @param expression 表达式,数值与符号之间必须用空格隔开。 */
public int calculate(String expression) { String[] strings = StringUtils.split(
expression, ' '); // 数值栈 Stack<Integer> numStack = new Stack<>(); // 符号栈 Stack<
String> operStack = new Stack<>(); for (String s : strings) { if (isNumber(s)) {
// 数值处理 if (numStack.isEmpty()) { // 如果数值栈为空,直接入栈 numStack.push(Integer.parseInt
(s)); } else if (isOpeningBracket(operStack.peek())) { // 如果符号栈栈顶是前括号,直接入栈
numStack.push(Integer.parseInt(s)); } else if (getPriority(operStack.peek()) ==
2) { // 如果符号栈栈顶的运算符优先级高,则取出符号栈栈顶元素,取出数值栈栈顶元素然后进行计算 // 并将计算结果重新入数值栈 int num1 =
numStack.pop(); int num2 = Integer.parseInt(s); int res = this.calc(num1, num2,
operStack.pop()); numStack.push(res); } else { // 其他情况直接入数值栈 numStack.push(
Integer.parseInt(s)); } } else if (isBracket(s)) { // 括号处理 if (isOpeningBracket(
s)) { // 如果是前括号直接入符号栈 operStack.push(s); } else { // 如果是后括号则完成括号内子式的计算 this.
calcBracket(numStack, operStack); } } else if (isOperator(s)) { // 运算符处理
operStack.push(s); } } // 依次取出符号栈和数值栈内的运算符和数值进行计算 while (!operStack.isEmpty()) {
int num2 = numStack.pop(); int num1 = numStack.pop(); int res = this.calc(num1,
num2, operStack.pop()); numStack.push(res); } return numStack.pop(); } /** *
计算括号内的表达式 */ private void calcBracket(Stack<Integer> numStack, Stack<String>
operStack) { // (12) if (isOpeningBracket(operStack.peek())) { operStack.pop();
highPriorityCalc(numStack, operStack); } else { //
经过优先级高先计算的规则,括号内不会出现乘法和除法,所以顺序计算即可。 int num2 = numStack.pop(); int num1 =
numStack.pop(); int res = this.calc(num1, num2, operStack.pop()); numStack.push(
res); calcBracket(numStack, operStack); } } /** * 高优先级运算符的运算 */ private void
highPriorityCalc(Stack<Integer> numStack, Stack<String> operStack) { if (this.
isOperator(operStack.peek()) && this.getPriority(operStack.peek()) == 2) { int
num2= numStack.pop(); int num1 = numStack.pop(); int res = this.calc(num1, num2,
operStack.pop()); numStack.push(res); highPriorityCalc(numStack, operStack); }
} private int calc(int num1, int num2, String s) { int res; switch (s) { case
"+": res = num1 + num2; break; case "-": res = num1 - num2; break; case "/": res
= num1 / num2; break; case "*": res = num1 * num2; break; default: throw new
RuntimeException("不能识别的符号"); } return res; } private boolean isNumber(String s)
{ return s.matches("\\d+"); } private boolean isOperator(String s) { return "+".
equals(s) || "-".equals(s) || "*".equals(s) || "/".equals(s); } private boolean
isBracket(String s) { return "(".equals(s) || ")".equals(s); } private boolean
isOpeningBracket(String s) { return "(".equals(s); } private int getPriority(
String s) { if ("+".equals(s) || "-".equals(s)) { return 1; } else if ("*".
equals(s) || "/".equals(s)) { return 2; } else { throw new RuntimeException(
"不识别此符号"); } } }
测试代码如下
public class InfixExpressionTest { @Test public void test() { String expression
= "3 + 6 - 18 / 2"; InfixExpression ie = new InfixExpression(); int res = ie.
calculate(expression); assertThat(res).isEqualTo(0); } @Test public void test2()
{ String expression = "3 + 3 * ( 26 - 16 / 2 ) / 2 + 2 - 20"; //
3+3*18/2-18=3+27-18=12 InfixExpression ie = new InfixExpression(); int res = ie.
calculate(expression); assertThat(res).isEqualTo(12); } }
以上代码已通过此测试代码。

技术
©2019-2020 Toolsou All rights reserved,
@Repository注解的作用mysql 修改主键golang一行代码将切片转成以分号分隔的字符串pytorch之ResNet18(对cifar10数据进行分类准确度达到94%)element-ui的el-date-picker组件获取值Mybatis映射文件Mapper.xml中#和$的区别雷军:两年前和卢伟冰喝酒到凌晨三点 钦佩其工作热情和能力SSM项目的excel文件上传并添加到数据库线上问题排查之HTTP状态码——415和406关于Bellman-Ford算法的个人理解