中缀表达式转后缀表达式c++
时间: 2023-10-23 22:03:14 浏览: 149
中缀表达式计算
中缀表达式转后缀表达式,是一种运算符写在操作数之后的表达式表示方法。下面是一个将中缀表达式转换为后缀表达式的算法:
1. 创建一个栈(称为运算符栈)和一个空字符串(用于存储后缀表达式)。
2. 从左到右扫描中缀表达式的每个元素。
3. 如果遇到操作数(即数字),则将其直接附加到后缀表达式的末尾。
4. 如果遇到操作符,检查运算符栈的栈顶元素:
a. 如果运算符栈为空,或者栈顶元素是左括号"(",则将该操作符入栈。
b. 如果当前的操作符比运算符栈的栈顶元素优先级高,则将该操作符入栈。
c. 如果当前的操作符比运算符栈的栈顶元素优先级低或相等,则将运算符栈的栈顶元素弹出并附加到后缀表达式的末尾,直到当前的操作符的优先级高于栈顶元素。
5. 如果遇到左括号"(",则将其入栈。
6. 如果遇到右括号")",则弹出运算符栈的元素并附加到后缀表达式的末尾,直到弹出一个左括号"("。
7. 将中缀表达式扫描完毕后,如果运算符栈不为空,则将栈中的所有元素依次弹出并附加到后缀表达式的末尾。
例如,对于中缀表达式"c = a + b * ( d * e + f ) - g",根据上述算法转换为后缀表达式为:"c a b d e * f + * + g -"。
注意:以上算法没有考虑操作符的结合性,如果需要添加结合性的支持,还需对算法进行适当修改。
阅读全文