数据结构作业：递归算法与中缀表达式转后缀表达式

"这是一份来自西南交通大学的数据结构课程的第二次作业，涵盖了堆栈、队列、串等知识。作业包含三个编程任务：1) 使用递归和非递归（堆栈）方法输出非零正整数的各位数字；2) 实现中缀表达式到后缀表达式的转换；3) 使用改进的KMP算法替换主串中的子串。提供的代码片段展示了部分解题思路，包括栈的操作和双向栈的初始化与压入、弹出元素的函数定义。" 作业解答详细说明： 1. 输出非零正整数的各位数字： - 递归方法：通过将整数除以10并取余数得到个位数字，然后对商继续进行相同操作，直到商为0。每次取余数后，打印空格分隔的数字。 - 非递归方法（堆栈）：将整数逆序存入堆栈，然后逐个弹出并打印，每弹出一个数字后加一个空格。 2. 中缀表达式到后缀表达式的转换： - 这是一个涉及运算符优先级的问题，可以使用栈来处理。遍历中缀表达式的每一个字符，如果是操作数，则直接输出；如果是左括号，入栈；如果是右括号，依次出栈并将运算符输出，直到遇到左括号；如果是运算符，根据优先级决定是否入栈或输出当前运算符。最后，将栈中剩余的运算符全部输出。 3. 主串中子串的替换（改进的KMP算法）： - KMP算法是一种提高字符串匹配效率的方法，避免了不必要的回溯。在原KMP算法基础上进行改进，当找到子串t1时，替换为t2，并记录替换次数。首先构建部分匹配表，然后在主串s中进行匹配，一旦出现匹配失败，根据部分匹配表确定下次匹配的起点，直到找到所有t1并完成替换。 此外，代码片段还给出了双向栈（TwoWayStack）的定义，包括结构体定义、初始化函数InitStack以及压入元素的Push函数。双向栈允许在两端进行压入和弹出操作，这在某些算法中非常有用，例如在实现非递归的数字拆分时。但代码中未提供Pop函数的完整实现，通常Pop函数会根据指定索引（0或1）从对应端弹出元素。