已知操作符包括‘ +’、‘ -’、‘ *’、‘ /’、‘ (’和‘ )’。将中缀表达式 a+b-a*((c+d)/e-f)+g 转换为后缀表达式 ab+acd+e/f-*-g+时,用栈来存放暂时还不能确定运算次序的操作符。若栈初始时为空,则转换过程中同时保存在栈中的操作符的最大个数是( )。
5
7
8
11
stack 操作符栈; for i=1 to n{ if 当前操作符是操作数 直接打印; else if 当前操作符是操作符{ if 当前操作符是'(' 压入栈内; else if 当前操作符是')' 不断弹出并打印栈顶元素直至栈顶为'('; 弹出栈顶; else if 当前操作符优先级高于栈顶操作符 || 栈为空 压入栈内; else 不断弹出并打印栈顶元素直至栈顶优先级不大于当前元素; 当前操作符入栈; } } 打印栈中剩余操作符;
标记:
一个左括号压入栈
一个右括号,连续弹出直到遇到左括号
一个运算符,如果优先级比栈顶元素高,直接压入,否则弹出栈顶元素,将自己压入(两种,优先级低或者同等优先级)
这道题你会答吗?花几分钟告诉大家答案吧!
扫描二维码,关注牛客网
下载牛客APP,随时随地刷题
优先级从低至高:(、+-、*/、^
回到本题,流程如下:(数字标明当前栈中元素个数)
遇+,入栈,1个
遇-,-的优先级不大于+,弹出+,压入-,1个
遇*,*的优先级大于-,入栈,2个
遇(,入栈,3个
遇(,入栈,4个
遇+,+的优先级大于(,入栈,5个
遇),弹出+,弹出(,3个
遇/,/的优先级大于(,入栈,4个
遇-,-的优先级不大于/,弹出/,压入-,4个
遇),弹出-,弹出(,2个
遇+,+的优先级不大于*,弹出*,压入+,2个
操作符遍历完毕,栈中最后自底而上为-和+,依次弹出。
综上,栈中元素最多的时候有5个。