解决问题的核心步骤

解解决决问问题题的的核核心心步步骤骤 1 构造一个 20 字节的栈 不够再 10 个 10 个地追加 2 从第一个字符开始检查 遇到左括号 进栈 遇见右括号时检查栈顶元素是 否与之相匹配 是则弹出栈顶元素 否 则返回 0 程序构造思想程序构造思想 主程序模块 char main 定义变量 定义指向栈的指针 读入字符串 调用 Match 函数 栈的初始化 InitStack 创建一个可以存储 20 个字节的栈 若创建失败 退出 压栈 PushStack 判断栈是否栈满 栈满 追加 若存储分配失败 退出 e 赋值给 top 所指向的单元 top 向上移一位 获取栈顶元素 GetTop 返回 top 1 所指单元的值 匹配函数 Match for 从首字符开始判断 遇到左括号 进栈 遇到右括号 和栈顶字符比较 与之匹配 栈顶元素弹栈 遇到不匹配的右括号 提示配对失败 返回 r 值 bool 函数 程序源代码程序源代码 include include include include include using namespace std define STACK INIT SIZE 20 define STACKINCREMENT 10 类型说明 typedef struct char base 设置栈底指针 char top 设置栈顶指针 int stacksize SqStack 构造一个栈 S void InitStack SqStack S S base char malloc STACK INIT SIZE 分配可以放得下个 整数的内存空间 if S base exit 0 存储分配失败 S top S base S stacksize STACK INIT SIZE 插入新的栈顶元素 e void Push SqStack S char e if S top S base S stacksize 栈满 追加存储空间 S base char realloc S base S stacksize STACKINCREMENT if S base exit 0 存储分配失败 S top S base S stacksize S stacksize STACKINCREMENT S top e S top 获取栈顶元素 char GetTop SqStack S if S top S base return 0 return S top 1 弹出栈顶元素 e char Pop SqStack S if S top S base return 0 栈空 返回 ERROR return S top 栈不空 用 e 返回栈顶元素 栈空 int Empty SqStack S if S base S top return 1 else return 0 匹配函数 bool Match char c 40 SqStack S int i bool r true InitStack S for i 0 i 20 i 从首元素开始判断 if c i 是 进栈 cout Push a parenthesis c i into the stack endl else if c i 是 弹栈 cout Success to match one pair of parenthesis endl else cout Fail to match a pair of parenthesis endl r false else if c i 是 弹栈 cout Success to match one pair of parenthesis endl else cout Fail to match a pair of parenthesis endl r false return r char main char c 40 SqStac