重启数据结构与算法4

[Ray-56]

重启数据结构与算法4

重启数据结构与算法，一些代码案例使用 Deno 与 TypeScript 实现，相关代码都在这里

1. 重启数据结构与算法1
2. 重启数据结构与算法2
3. 重启数据结构与算法3
4. 重启数据结构与算法4

栈

堆栈（英语：stack）又称为栈或堆叠，是计算机科学中的一种抽象数据类型，只允许在有序的线性数据集合的一端（称为堆栈顶端，英语：top）进行加入数据（英语：push）和移除数据（英语：pop）的运算。因而按照后进先出（LIFO, Last In First Out）的原理运作。
常与另一种有序的线性数据集合队列相提并论。
堆栈常用一维数组或链表来实现。

应用场景：

• 处理递归调用
• 表达式转换
• 二叉树的遍历
• 图的深度优先 depth-first

数组模拟

先使用数组进行模拟栈

import { readLines } from "https://deno.land/std/io/mod.ts";

class ArrayStack {
    private stack: number[] = [];
    private maxSize: number;
    private top = -1;

    constructor(maxSize: number) {
        this.maxSize = maxSize;
    }
    public isFull() {
        return this.top === this.maxSize - 1;
    }
    public isEmpty() {
        return this.top === -1;
    }
    public push(value: number) {
        if (this.isFull()) {
            console.log('栈已满！');
            return;
        }
        this.stack[++this.top] = value;
    }
    public pop(): number {
        if (this.isEmpty()) {
            console.error('空栈，无法出栈！');
            return -1;
        }
        return this.stack[this.top--];
    }
    public showList() {
        for (let i = this.top; i >= 0; i--) {
            console.log(`stack[${i}] = ${this.stack[i]}`)
        }
    }
}

const dict = {
    show: 'show - 显示栈中数据',
    push: 'push - 入栈',
    pop: 'pop - 出栈',
}

window.onload = async function main() {
    console.table(dict);
    const stack = new ArrayStack(3);
    for await (const line of readLines(Deno.stdin)) {
        switch (line) {
            case 'show':
                stack.showList();
                break;
            case 'push':
                const ret = await readLines(Deno.stdin).next();
                const value = Number(ret.value.trim());

                if (typeof value !== 'number' || isNaN(value)) {
                    console.log('输入内容不为数字！');
                    break;
                }
                stack.push(value);
                break;
            case 'pop':
                const valPop = stack.pop();
                console.log(`${valPop} 出栈`);
                break;
            default:
                // 默认不作处理
        }
    }
}

测试结果：

链表模拟

接着使用链表模拟

class Node {
    public value: number;
    public next: Node | null = null;
    constructor(value: number) {
        this.value = value;
    }
}

class SingleLinkedList {
    private head = new Node(-1);
    public add(node: Node) {
        let temp = this.head;
        while (temp.next) {
            temp = temp.next;
        }
        temp.next = node;
    }
    public del(): number {
        let temp = this.head;
        if (!temp.next) {
            console.log('空链表！');
            return -1;
        }
        while (temp.next) {
            if (temp.next.next === null) break;
            temp = temp.next;
        }
        const ret = temp.next!.value;
        temp.next = null;
        return ret;
    }
    public show() {
        let temp = this.head;
        while (temp.next !== null) {
            temp = temp.next;
            console.log(`current node value = ${temp.value}`);
        }
    }
}

class LinkedListStack {
    private stack: SingleLinkedList;
    private maxSize: number;
    private top = -1;
    constructor(maxSize: number) {
        this.stack = new SingleLinkedList();
        this.maxSize = maxSize;
    }
    private isFull() {
        return this.top === this.maxSize - 1;
    }
    private isEmpty() {
        return this.top === -1;
    }

    public push(value: number) {
        if (this.isFull()) {
            console.log('栈已满！');
            return;
        }
        this.top++;
        this.stack.add(new Node(value));
    }
    public pop(): number {
        if (this.isEmpty()) {
            console.error('空栈，无法出栈！');
            return -1;
        }
        this.top--;
        return this.stack.del();
    }
    public showList() {
        this.stack.show();
    }
}

window.onload = function main() {
    const stack = new LinkedListStack(3);
    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.pop();
    stack.pop();
    stack.showList();
    // 输入：current node value = 1
}

计算表达式

• 前缀表达式：波兰表示法（Polish notation，或波兰记法），是一种逻辑、算术和代数表示方法，其特点是操作符置于操作数的前面，因此也称做前缀表示法。如果操作符的元数（arity）是固定的，则语法上不需要括号仍然能被无歧义地解析。波兰记法是波兰数学家扬·武卡谢维奇1920年代引入的，用于简化命题逻辑。 ---- 维基百科

• 中缀表达式：中缀表示法（或中缀记法）是一个通用的算术或逻辑公式表示方法， 操作符是以中缀形式处于操作数的中间（例：3 + 4）。与前缀表达式（例：+ 3 4 ）或后缀表达式（例：3 4 + ）相比，中缀表达式不容易被电脑解析，但仍被许多程序语言使用，因为它符合人们的普遍用法。
  与前缀或后缀记法不同的是，中缀记法中括号是必需的。计算过程中必须用括号将操作符和对应的操作数括起来，用于指示运算的次序。 ---- 维基百科

• 后缀表达式：逆波兰表示法（Reverse Polish notation，RPN，或逆波兰记法），是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式方式，在逆波兰记法中，所有操作符置于操作数的后面，因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级。
  逆波兰结构由弗里德里希·鲍尔（Friedrich L. Bauer）和艾兹格·迪科斯彻在1960年代早期提议用于表达式求值，以利用堆栈结构减少计算机内存访问。逆波兰记法和相应的算法由澳大利亚哲学家、计算机学家查尔斯·汉布尔（Charles Hamblin）在1960年代中期扩充[1][2]
  在1960和1970年代，逆波兰记法广泛地被用于台式计算器，因此也在普通公众（如工程、商业和金融等领域）中使用。 ---- 维基百科

中缀表达式计算器

步骤：

1. 创建两个栈，数字栈numStack和符号栈operStack
2. 遍历表达式
3. 遇到数字入数字栈
4. 遇到符号
   • 符号栈为空，直接入符号栈
   • 符号栈不为空，与栈顶符号优先级比较
     • 小于等于，从数字栈出两个与当前符号计算后将结果入数字栈
     • 大于，直接入符号栈
5. 数字栈中的最后一个为表达式结果

这里直接使用上方数组模拟栈的类

import ArrayStack from './ArrayStack.ts';

class ArrayStack1<T> extends ArrayStack<T> {
    /**
     * 查看栈顶
     */
    public peek(): T {
        if (this.isEmpty()) {
            console.log('空栈，无法查看！');
        }
        return this.stack[this.top];
    }
    /**
     * 返回符号的优先级，由自己定义
     * @param oper - 符号
     */
    public static priority(oper: string): number {
        let ret = -1;
        if (['+', '-'].includes(oper)) {
            ret = 1;
        } else if (['*', '/'].includes(oper)) {
            ret = 2;
        }

        return ret;
    }
    /**
     * 判断是否为符号
     * @param val - 需要判断的值
     */
    public static isOper(val: string): boolean {
        return ['+', '-', '*', '/'].includes(val);
    }
    public static cal(n1: number, n2: number, oper: string): number {
        let ret = 0;
        switch (oper) {
            case '+':
                ret = n1 + n2;
                break;
            case '-':
                ret = n1 - n2;
                break;
            case '*':
                ret = n1 * n2;
                break;
            case '/':
                ret = n1 / n2;
                break;
        }
        return ret;
    }
}

function run(expression: string) {
    const numStack = new ArrayStack1(10);
    const operStack = new ArrayStack1<string>(10); // 这里使用泛型处理，如果不用泛型可以将符号转为 charCode
    let index = 0; // 表达式的下标
    while (index < expression.length) {
        const ch = expression.substring(index, index + 1);
        if (ArrayStack1.isOper(ch)) {
            if (operStack.isEmpty()) {
                operStack.push(ch);
            } else {
                if (ArrayStack1.priority(ch) <= ArrayStack1.priority(operStack.peek())) {
                    const num1 = numStack.pop() as number;
                    const num2 = numStack.pop() as number;
                    const oper = operStack.pop() as string;
                    const ret = ArrayStack1.cal(num2, num1, oper);
                    numStack.push(ret);
                    operStack.push(ch);
                } else {
                    operStack.push(ch);
                }
            }
        } else {
            numStack.push(Number(ch));
        }
        index++;
    }
    // 根据观察可知，符号栈为空时，表达式的值为数字栈的最后一位
    while (!operStack.isEmpty()) {
        const num1 = numStack.pop() as number;
        const num2 = numStack.pop() as number;
        const oper = operStack.pop() as string;

        // 注意，中缀表达式计算是 num2 oper num1
        const ret = ArrayStack1.cal(num2, num1, oper);
        numStack.push(ret);
        numStack.showList();
    }

    console.log(`表达式 ${expression} = ${numStack.pop()}`); // 输出：表达式 3+2*6-2 = 13
}

// 对计算器进行计算，中缀表达式
window.onload = function main() {
    run('3+2*6-2');
}

其实这里还是有一点问题的，如果表达式为34+2*6-2，上面的代码没有对多位数进行处理

...
function run(expression: string) {
    ...
    if (ArrayStack1.isOper(ch)) {
        ...
    } else {
        // 这里加入对多位数的处理
        let keepNum = ch;
        const nextCh = expression.substring(index + 1, index + 2);
        // 下一位不是符号则合并值
        if (!ArrayStack1.isOper(nextCh)) {
            keepNum += nextCh;
            index++; // 移动指针
        }

        numStack.push(Number(keepNum));
    }
}

// 对计算器进行计算，中缀表达式
window.onload = function main() {
    run('33+20*6-2'); // 表达式 33+20*6-2 = 151
}
...

逆波兰计算器

使用后缀表达式（逆波兰）来实现计算器

为了方便计算，我们约定

• 每个值都用空格隔开3 4 + 5 * 6 -
• 只计算多位整数

import ArrayStack from './ArrayStack.ts';

class PolandNotation {
    private suffixExpression: string;
    private list: string[];
    constructor(suffixExpression: string) {
        this.suffixExpression = suffixExpression;
        this.list = this.toList();
    }
    private toList(): string[] {
        return this.suffixExpression.split(' ');
    }
    public calculate(): number {
        const stack = new ArrayStack<number>(10);
        for (let i = 0; i < this.list.length; i++) {
            const item = this.list[i];
            // 正则判断匹配是否为数字
            if (/\d/.test(item)) {
                stack.push(Number(item));
            } else {
                const num1 = stack.pop() as number;
                const num2 = stack.pop() as number;
                let ret = 0;
                if (item === '+') {
                    ret = num2 + num1;
                } else if (item === '-'){
                    ret = num2 - num1;
                } else if (item === '*'){
                    ret = num2 * num1;
                } else if (item === '/'){
                    ret = num2 / num1;
                }
                stack.push(ret);
            }
        }

        const ret = stack.pop() as number;
        return ret;
    }
}

window.onload = function mian() {
    const pn = new PolandNotation('3 4 + 5 * 6 -');
    console.log(pn.calculate()); // 29
}

下面加入中缀转后缀，转换步骤在注释中

/**
 * 符号优先级
 */
enum OperationLevel {
    Add = 1,
    Sub = 1,
    Mul = 2,
    Div = 2
}

/**
 * 获取符号优先级
 * @param operation - 符号
 */
function getOperationLevel(operation: string): number {
    let ret = 0;
    switch (operation) {
        case '+':
            ret = OperationLevel.Add;
            break;
        case '-':
            ret = OperationLevel.Sub;
            break;
        case '*':
            ret = OperationLevel.Mul;
            break;
        case '/':
            ret = OperationLevel.Div;
            break;
        default:
            // 不作处理
            break;
    }
    return ret;
}

class PolandNotation1 {
    public static toInfixExpressionList(s: string): string[] {
        let ret: string[] = [];
        let index = 0; // 遍历 s 的指针
        let str = ''; // 多位数处理
        let c = ''; // 每个字符

        do {
            // 判断非数字
            if (((c = s.charAt(index)).charCodeAt(0) < 48) || ((c = s.charAt(index)).charCodeAt(0) > 57)) {
                ret.push(c);
                index++;
            } else {
                // 处理多位数
                while (index < s.length && (c = s.charAt(index)).charCodeAt(0) >= 48 && (c = s.charAt(index)).charCodeAt(0) <= 57) {
                    str += c; // 拼接
                    index++;
                }
                ret.push(str);
                str = '';
            }
        } while (index < s.length);

        return ret;
    }
    public static parseSuffixExpressionList(ls: string[]): string[] {
        const s1: string[] = []; // 符号栈
        const ret: string[] = []; // 结果数组；按照算法中这里应该也是栈，存入后还需要翻转，所以这里直接使用了数组
        for (let item of ls) {
            // 正则判断是数字。 \d 匹配数字，+ 表示重复一次或多次，* 重复零次或多次
            if (/\d+/.test(item)) {
                ret.push(item);
            } else if (item === '(') {
                // 是左括号，直接入符号栈
                s1.push(item);
            } else if (item === ')') {
                // 当匹配到右括号时
                //  1. 从符号栈出栈，加入到结果数组中，直到栈顶为左括号
                //  2. 将左括号也出栈
                while (s1[s1.length - 1] !== '(') { // 这里 s1[s1.length - 1] 相当于 s1.peek()，查看栈顶
                    ret.push(s1.pop() as string);
                }
                s1.pop(); // 左括号出栈，成对消除括号
            } else {
                // 其它符号
                //  1. 判断优先级，item 优先级 <= s1栈顶运算符时，出符号栈加入结果数组
                //  2. 当前符号入符号栈
                while (s1.length !== 0 && getOperationLevel(item) <= getOperationLevel(s1[s1.length - 1])) {
                    ret.push(s1.pop() as string);
                }
                s1.push(item);
            }
        }
        // 最后将符号栈清空加入结果数组
        while (s1.length) {
            ret.push(s1.pop() as string);
        }

        return ret;
    }
}

window.onload = function mian() {
    const str = '1+((20+3)*4)-5';
    const infixList = PolandNotation1.toInfixExpressionList(str);
    const suffixList = PolandNotation1.parseSuffixExpressionList(infixList);
    console.log(PolandNotation.calculate(suffixList)); // 88
}

下期预告

• 递归