B. 栈帧

内存限制:16 MiB 时间限制:100 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

在代码被编译时,编译器能够知道函数需要多少的栈空间,并在调用函数时,在栈上开辟相应的大小。在这个题目中,我们将此称为 帧大小

在此题中,Musha 想要你维护一下函数的调用栈,并分析函数的调用深度与栈空间的使用大小。

具体而言,你可以知道程序中所有函数的函数名帧大小

当调用一个函数时,将这个函数入栈,并扩充栈空间。当函数返回时,将其出栈,并释放栈空间

在这一个题目中,Musha 精心设计的编译器还支持一键切换栈帧,具体而言,将函数调用栈从栈底到栈顶依次编号为 0, 1, 2, ...,切换栈帧到 时,编号大于 的函数全部出栈,并释放栈空间。

输入指令

指令 含义 样例
call func 调用函数 call main
return 栈顶函数返回 return
frame x 切换栈帧到 frame 1

输入格式

输入分为两部分。

首先是 行内容,第一行一个正整数 ,表示可供调用的函数的总数,接下来 行,每行一个仅由英文字母组成的字符串,以及一个使用空格隔开的数字,表示当前程序中存在的函数以及它的帧大小。函数没有重名。

行及以后,为不定行的函数调用、返回、切换栈帧的指令,保证完全合法,且能够正常结束。首先调用的一定是 main 函数,当所有函数全部 return 之后(也即帧为空时),输入结束,程序结束。

,函数名仅由英文字母组成,不超过 30 个字符,帧大小为小于 2048 的正整数。

行一定为 call main。指令总数不超过 100 条。

输出格式

输出共 4 行。

第一行一个整数,表示调用栈的最大高度(栈中同时存在的函数个数的最大值),第二行输出此时栈中依次调用的函数以及它们各自的帧大小。

第三行一个整数,表示调用栈中函数的帧大小之和的最大值,第四行输出此时栈中依次调用的函数以及它们各自的帧大小。

输出函数时,按照 func(size) 的格式输出,如 main(1024),不同函数间用一个空格隔开。

样例

输入样例

4
main 1024
calc 100
sin 20
cos 22
call main
call calc
call calc
return
call sin
return
call cos
call sin
frame 2
return
return
return

输出样例

4
main(1024) calc(100) cos(22) sin(20) 
1224
main(1024) calc(100) calc(100)
编辑器加载中 …
通告标题

通告内容

已知晓