假设不含括号的表达式由单字母变量和双目四则运算符构成,试写一个算法,将一个通常书写形式且书写正确的表达式转换成逆波兰式。其中precede(char x,char y) 为判断x,y优先级,该算法可以直接调用。
时间: 2023-04-30 14:00:49 浏览: 92
表达式的求值,表达式的求值
算法如下:
1. 初始化一个空栈S和一个空字符串RPN。
2. 从左到右扫描表达式中的每个元素,如果是数字或字母,则直接加入RPN字符串中。
3. 如果是运算符,则进行如下操作:
a. 如果栈S为空或栈顶元素为左括号,则将该运算符入栈。
b. 如果该运算符优先级大于栈顶运算符,则将该运算符入栈。
c. 如果该运算符优先级小于或等于栈顶运算符,则将栈顶运算符弹出并加入RPN字符串中,直到栈顶运算符优先级小于该运算符或栈为空,然后将该运算符入栈。
d. 如果该运算符为右括号,则将栈顶元素弹出并加入RPN字符串中,直到遇到左括号为止,左括号不加入RPN字符串中。
4. 扫描完表达式后,如果栈S不为空,则将栈中所有元素依次弹出并加入RPN字符串中。
5. 返回RPN字符串作为逆波兰式。
其中precede(char x,char y)为判断x,y优先级的函数,可以根据具体需求自行实现。
阅读全文