中缀表达式4 * 3 +(6 * 3 - 12)转换为后缀表达式,则s的最小大小必须为:
时间: 2023-09-15 09:02:37 浏览: 279
中缀表达式转换为后缀表达式
要将中缀表达式转换为后缀表达式,可以使用栈的数据结构来辅助转换。具体步骤如下:
1. 创建一个空栈和一个空串s,用于存放后缀表达式。
2. 从左到右遍历中缀表达式的每个元素。
3. 遇到数字时,直接将其添加到s中。
4. 遇到运算符时,判断其与栈顶运算符的优先级。如果栈顶运算符的优先级高于或等于该运算符的优先级,将栈顶运算符添加到s中,再将该运算符压入栈中;如果栈顶运算符的优先级低于该运算符的优先级,直接将该运算符压入栈中。
5. 遇到左括号时,直接将其压入栈中。
6. 遇到右括号时,将栈顶的元素弹出并添加到s中,直到遇到左括号。将左括号从栈中弹出,但不添加到s中。
7. 将栈中剩余的运算符依次弹出并添加到s中。
根据这个转换规则,将中缀表达式4 * 3 (6 * 3 - 12)转换为后缀表达式的过程如下:
1. 遇到数字4,将其添加到s中。
2. 遇到运算符*,直接将其压入栈中。
3. 遇到数字3,将其添加到s中。
4. 遇到左括号(,将其压入栈中。
5. 遇到数字6,将其添加到s中。
6. 遇到运算符*,栈顶运算符优先级较低,将其压入栈中。
7. 遇到数字3,将其添加到s中。
8. 遇到运算符-,栈顶运算符优先级较低,将其压入栈中。
9. 遇到数字12,将其添加到s中。
10. 遇到右括号),将栈顶运算符弹出并添加到s中,一直到遇到左括号(,将左括号从栈中弹出。
11. 遍历完毕,将栈中剩余的运算符依次弹出并添加到s中。
最终得到的后缀表达式为4 3 * 6 3 * 12 - -
由此可见,s的最小大小必须为13。
阅读全文