数据结构与算法（二）——前缀、中缀、后缀表达式

一、前缀表达式（波兰表达式）

1.1、计算机求值

从右至左扫描表达式，遇到数字时，将数字压入堆栈。遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素和次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果

例如：
(3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6。针对前缀表达式求值步骤如下：
1）从右至左扫描，将 6、5、4、3压入堆栈；
2）遇到 + 运算符，因此弹出3和4（3为栈顶元素，4为次顶元素），计算出3+4的值，得 7，再将7入栈；
3）接下来是×运算符，因此弹出 7 和 5，计算出 7×5=35，将35入栈；
4）最后是 - 运算符，计算出 35-6 的值，即 29，由此得出最终结果。

二、中缀表达式

1）中缀表达式就是常见的运算符表达式，如 (3+4)×5-6
2）中缀表达式的求值是我们人类最熟悉的，但是对计算机来说缺不好操作。因此，在计算结果时，往往会将中缀表达式转成其他表达式来操作（一般转成后缀表达式）
中缀表达式 - 栈实现综合计算器

三、后缀表达式（逆波兰表达式）

1）后缀表达式又称 逆波兰表达式，与前缀表达式相近，只是运算符位于操作数之后；
2）举例说明：(3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 -
3）在这里插入图片描述

3.1、计算机求值

从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到操作符时，弹出栈顶的两个数，用运算符对它们做出相应的计算（次顶元素和栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果。

例如：
(3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 -。针对后缀表达式求值步骤如下：
1）从左至右扫描，将 3 和 4 压入堆栈；
2）遇到 + 运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得 7，再将7入栈；
3）接下来是×运算符，因此弹出 5 和 7，计算出 7×5=35，将35入栈；
4）将 6 入栈
5）最后是 - 运算符，计算出 35-6 的值，即 29，由此得出最终结果。

3.2、逆波兰计算器分析与实现

我们完成一个逆波兰计算器，要求完成如下任务：
1）输入一个逆波兰表达式(后缀表达式)，使用栈(Stack), 计算其结果
2）支持小括号和多位数整数，因为这里我们主要讲的是数据结构，因此计算器进行简化，只支持对整数的计算。
3）思路分析
4）代码完成

package Algotithm.stackimport java.utilobject PolandNotation {def main(args: Array[String]): Unit = {//先定义一个逆波兰表达式val suffixExpression = "3 4 + 5 * 6 -"//思路//1.先将 suffixExpression => arrayList中//2.将arrayList传递给一个方法，遍历 配合栈完成计算val list = getListString(suffixExpression)println(list)val result = calculate(list)println(s"计算的结果时$result")}//将逆波兰表达式，依次将数据和运算符 放入到arrayList中def getListString(string: String): util.ArrayList[String] = {//将arrayList分割val strings = string.split(" ")val list = new util.ArrayList[String]()strings.foreach(elem => list.add(elem))list}//完成计算def calculate(list: util.ArrayList[String]): Int = {//创建栈，只需要一个栈即可val stack = new util.Stack[String]//遍历lslist.forEach(elem => {if (elem.matches("\\d+")) { //匹配的是多位数//入栈stack.push(elem)} else {//pop出两个数，并运算，再入栈val num2 = stack.pop().toIntval num1 = stack.pop().toIntval res = elem match {case "+" => num1 + num2case "-" => num1 - num2case "*" => num1 * num2case "/" => num1 / num2case _ => throw new Exception("运算符有误")}stack.push(res.toString)}})//最后留在stack中的就是运算结果stack.pop().toInt}
}

在这里插入图片描述

四、中缀转后缀表达式

具体步骤如下：
1）初始化两个栈：运算符栈s1和储存中间结果的栈s2；
2）从左至右扫描中缀表达式；
3）遇到操作数时，将其压s2；
4）遇到运算符时，比较其与s1栈顶运算符的优先级：
（1）如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
（2）否则，若优先级比栈顶运算符的高，也将运算符压入s1；
（3）否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4.1)与s1中新的栈顶运算符相比较；
5）遇到括号时：
（1）如果是左括号“(”，则直接压入s1
（2）如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
6）重复步骤2至5，直到表达式的最右边
7）将s1中剩余的运算符依次弹出并压入s2
8）依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式

方法：将中缀表达式转成对应的List

  //方法：将 中缀表达式转成对应的Listdef toInfixExpressionList(s: String): util.ArrayList[String] = {//定义一个list，存放中缀表达式 对应的内容val ls = new util.ArrayList[String]()var i = 0 //指针，用于遍历 lsvar str = "" //对多位数的拼接var c: Char = 0 //每遍历到一个字符，就放入到cwhile (i < s.length) {//如果c是一个非数字，需要加入到lsc = s.charAt(i)if (s.charAt(i) < 48 || s.charAt(i) > 57) {ls.add("" + s.charAt(i))i += 1} else { //如果是一个数，需要考虑多位数str = ""while (i < s.length && s.charAt(i) >= 48 && s.charAt(i) <= 57) {str += s.charAt(i)i += 1}ls.add(str)}}ls}

在这里插入图片描述

注意：在 while 中必须要加该判断，否则会下标越界异常。

定义优先级

class Operation {private val ADD = 1private val SUB = 1private val MUL = 2private val DIV = 2//返回对应的优先级数字def getValue(operation: String): Int = {val result = operation match {case "+" => ADDcase "-" => SUBcase "*" => MULcase "/" => DIVcase _ => 0}result}
}

中缀表达式list => 后缀表达式list

  //方法：将得到的中缀表达式list => 后缀表达式listdef parseSuffixExpressionList(ls: List[String]): util.ArrayList[String] = {//定义两个栈val s1 = new util.Stack[String] //符号栈//说明：因为s2在整个操作中没有pop，且后面还要逆序输出//因此不用stack，直接使用listval s2 = new util.ArrayList[String] //存储中间结果的list//遍历lsls.foreach(elem => {//如果是一个数，入s2if (elem.matches("\\d+")) {s2.add(elem)} else if (elem.equals("(")) {s1.push(elem)} else if (elem.equals(")")) {//如果是")"，则依次弹出s1栈顶的运算符并压入s2，直到遇到"("while (!s1.peek().equals("(")) {s2.add(s1.pop())}s1.pop() //将 ( 弹出s1栈，消除括号} else {//当elem运算符优先级 ≤ s1栈顶运算符//比较优先级高低的方法while (s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(elem)) {s2.add(s1.pop())}//将elem压入栈中s1.push(elem)}})//将s1剩余的运算符依次弹出并加入s2while (s1.size() != 0) {s2.add(s1.pop())}s2  //因为是存放到list，因此按顺序输出就是后缀表达式}

主函数

def main(args: Array[String]): Unit = {//完成将一个中缀表达式转成后缀表达式的功能//说明//1.1+((2+3)*4)-5 => 1 2 3 + 4 * 5 -//2.因为直接对str操作不方便，因此先将 str 转成中缀的list//3.将得到的中缀表达式list => 后缀表达式listval expression = "1+((2+3)*4)-5"val infixExpressionList = toInfixExpressionList(expression)println(s"$infixExpressionList")val suffixExpressionList = parseSuffixExpressionList(infixExpressionList)println(s"对应的后缀表达式 => $suffixExpressionList")}