- package Algotithm.stack
-
- object Calculator {
- def main(args: Array[String]): Unit = {
- val expression = "3+2*6-2"
- //创建两个栈:数栈、符号栈
- val numStack, operStack = new ArrayStack2(10)
- //定义需要的相关变量
- var index, num1, num2, oper, res = 0 //用于扫描
- var ch: Char = ' ' //每次扫描得到的char保存到ch
- var keepNum: String = ""
- //开始循环扫描入栈
- while (index < expression.length) {
- ch = expression.charAt(index)
- //判断是什么
- if (operStack.isOper(ch)) {
- if (operStack.isEmpty) {
- //如果为空直接入栈
- operStack.push(ch)
- } else {
- //如果不为空
- if (operStack.priority(ch) <= operStack.priority(operStack.peek())) {
- //从数栈中pop出两个数进行运算
- num1 = numStack.pop()
- num2 = numStack.pop()
- oper = operStack.pop()
- res = numStack.cal(num1, num2, oper)
- //把运算结果入数栈
- numStack.push(res)
- //当前符号入符号栈
- operStack.push(ch)
- } else {
- operStack.push(ch)
- }
- }
- } else {
- //如果是数,则直接入数栈
- //numStack.push(ch - 48)
- //1.当处理多位数时,不能发现一个数就立即入栈。因为也可能是多位数
- //2.在处理数时,需要像exp表达式后再看一位。如果是数就继续扫描。如果是符号再入栈
- //3.定义一个字符串变量,用于拼接
-
- //处理多位数
- keepNum += ch
- //如果ch已经是exp的最后一位,就直接入栈
- if (index == expression.length - 1) {
- numStack.push(keepNum.toInt)
- } else {
- //判断下一个字符是不是数字。如果是数字,就继续扫描。如果是运算符,则入栈
- if (operStack.isOper(expression.charAt(index + 1))) {
- //如果后一位时运算符,则入栈
- numStack.push(keepNum.toInt)
- //keepnum清空
- keepNum = ""
- }
- }
-
- }
- index = index + 1
- }
-
- while (!operStack.isEmpty) {
- //如果符号栈为空,则计算到最后的结果,数栈中只有一个数字
- num1 = numStack.pop()
- num2 = numStack.pop()
- oper = operStack.pop()
- res = operStack.cal(num1, num2, oper)
- numStack.push(res) //入栈
- }
- println(s"表达式 $expression = ${numStack.pop()}")
- }
- }
-
- //先创建一个栈
- class ArrayStack2 {
- private var maxSize: Int = _
- private var stack: Array[Int] = _
- private var top = -1
-
- //构造器
- def this(maxSize: Int) {
- this
- this.maxSize = maxSize
- stack = new Array[Int](this.maxSize)
- }
-
- //栈满
- def isFull: Boolean = {
- top == maxSize - 1
- }
-
- //栈空
- def isEmpty: Boolean = {
- top == -1
- }
-
- //返回当前栈顶的值
- def peek(): Int = {
- stack(top)
- }
-
- //入栈-push
- def push(value: Int): Unit = {
- if (isFull) {
- println(s"栈满")
- return
- }
- top = top + 1
- stack(top) = value
- }
-
- //出栈-pop
- def pop(): Int = {
- if (isEmpty) {
- throw new RuntimeException(s"栈空,没有数据")
- }
- val value = stack(top)
- top = top - 1
- value
- }
-
- //显示栈的情况【遍历栈】
- def list: Unit = {
- if (isEmpty) {
- println(s"栈空,没有数据")
- return
- }
- //需要从栈顶开始显示
- for (i <- 0 to top) {
- println(s"stack=${stack(top - i)}")
- }
- }
-
- //返回运算符的优先级,优先级为自定义
- //优先级使用数字表示。数字越大,优先级越高
- def priority(oper: Int): Int = {
- val ret = oper match {
- case '*' | '/' => 1
- case '+' | '-' => 0
- case _ => -1
- }
- ret
- }
-
- //判断是不是一个运算符
- def isOper(value: Char): Boolean = {
- value.equals('+') ||
- value.equals('-') ||
- value.equals('*') ||
- value.equals('/')
- }
-
- //计算方法
- def cal(num1: Int, num2: Int, oper: Int): Int = {
- var res: Int = 0 //用于存放计算的结果
- res = oper match {
- case '+' => num1 + num2
- case '-' => num2 - num1
- case '*' => num1 * num2
- case '/' => num2 / num1
- }
- res
- }
-
- }
Scala在模式匹配+偏函数的结合应用其灵活度太高了,,用顺手了习惯了之后会比Java简化很多。变量声明时也不用像Java一样一个变量new一次对象,可以像下面这样: