灵鹊做题网表达式求值中缀表达式转换为后缀表达式,并求值,（C语言）
来源：学生作业帮 编辑：灵鹊做题网作业帮 分类：综合作业 时间：2024/04/24 14:06:08
表达式求值
中缀表达式转换为后缀表达式,并求值,（C语言）
中缀表达式转换为后缀表达式,并求值,（C语言）
从算法来说,要考虑中缀的运算符优先级,括号等,可以使用简单语法制导翻译,去看编译原理书吧,从数据结构来说,可以使用二元树和栈.使用二元树就是先建立表达式的树,然后后根遍历即可.难点在建立树.
使用栈的算法也很多,说个好想的.假设表达式的字符来自输入流in,建立栈A存放运算符,B存放结果,从in读入一个操作数压进B,读入一个运算符压进A,如此反复.
1.读入一个元素e
2.如果e是操作数或者(,压入B,跳转到1
3.如果e是运算符(不包含括号),跳转到3.1
4.如果e是),跳转到4.1
5.如果e是EOF,即输入流结束,反复弹出A栈顶压入B,直到A为空,算法结束,B从栈底到栈顶的符号即为后缀表达式（需要把B翻个个儿^_^）
3.1.判断A的栈定符号t,如果t不为(,且优先级大于等于e,则弹出t压入B,跳转到4,如果t为空,即栈中为空,或其他情况直接把e压入A,跳转到1
4.1.弹出A的栈顶压入到B,如此反复直到弹出的符号为(,(和)不要压入B,跳转到1
这是我临时想的,可能还有bug,或描述不清的地方,如果上网搜的话应该有很多源代码的,如果学过编译原理的话还可以有更好的算法,这个算法没考虑容错性.
使用栈的算法也很多,说个好想的.假设表达式的字符来自输入流in,建立栈A存放运算符,B存放结果,从in读入一个操作数压进B,读入一个运算符压进A,如此反复.
1.读入一个元素e
2.如果e是操作数或者(,压入B,跳转到1
3.如果e是运算符(不包含括号),跳转到3.1
4.如果e是),跳转到4.1
5.如果e是EOF,即输入流结束,反复弹出A栈顶压入B,直到A为空,算法结束,B从栈底到栈顶的符号即为后缀表达式（需要把B翻个个儿^_^）
3.1.判断A的栈定符号t,如果t不为(,且优先级大于等于e,则弹出t压入B,跳转到4,如果t为空,即栈中为空,或其他情况直接把e压入A,跳转到1
4.1.弹出A的栈顶压入到B,如此反复直到弹出的符号为(,(和)不要压入B,跳转到1
这是我临时想的,可能还有bug,或描述不清的地方,如果上网搜的话应该有很多源代码的,如果学过编译原理的话还可以有更好的算法,这个算法没考虑容错性.