导航菜单
首页 >  用栈实现表达式计算考研  > 用栈实现表达式转换

用栈实现表达式转换

中缀转后缀:

从左到右依次扫描中缀表达式,遇到操作数就直接写出来(顺序是从前往后写),遇到运算符时,判断当前运算符与栈顶运算符的优先级,如果当前运算符的优先级小于或者等于栈顶元素运算符的优先级,就把栈顶运算符出栈,并将其写入当前结果表达式中(这个比较是个循坏,依次把当前元素和新的栈顶元素进行比较,如果还是小于等于则继续出栈,知道比较的是结果是大于栈顶运算符优先级则把当前运算符出栈)。 对于表达式中含有括号,当遇到左括号则直接入栈,当栈顶元素是左括号时则扫描的元素全入栈,当扫描的运算符是右括号时则执行一系列出栈操作,把当前栈中从栈顶到左括号的元素全部出栈,并将其写入结果表达式中,把括号丢弃。 最后当扫描完中缀表达式中所有字符时,此时若栈中还有剩余的运算符,则将其全部出栈并写入结果表达式中。 在这里插入图片描述

描述:首先把操作数a写入结果表达式,然后把运算符+压入栈中,然后把b写入结果表达式,然后运算符-的优先级等于栈顶元素+的优先级所以+出栈写入结果表达式,然后栈空所以把-运算符压入栈中,然后把a写入结果表达式,由于乘号运算符的优先级大于栈顶元素-的优先级,所以把乘号压入栈中,然后把两个左括号压入栈中,把c写入结果表达式,把运算符+压入栈中,把d写入结果表达式,遇到右括号,把与左括号之间的元素全部出栈并把括号丢弃掉。紧着着是运算符/,由于此时栈顶元素是左括号所以直接入栈,把e写入结果表达式,由于-运算符的优先级小于/所以/出栈,然后此时栈顶元素是左括号所以把-压入栈中,遇到右括号,把与左括号之间的元素依次出栈并把括号丢弃。由于运算符+的优先级小于乘号,所以乘号出栈,又等于-的优先级所以-出栈,此时栈空把+压入栈中,把操作数g写入结果表达式,此时已经扫描完表达式中所有字符,所以把栈中所剩的+出栈。 注意:本例中转换过程中在栈中的操作符的最大个数是5

中缀转前缀:

和转前转前缀式一个相反的过程,这个需要从右往左依次扫描。写结果表达式是从后往前写。 遇到右括号入栈遇到左括号把它们之间的元素全部出栈。还有一点,在转后缀时,如果此时运算符的优先级小于或者等于栈顶运算符优先级则出栈,而在转前缀时是小于。 后缀转前缀:每次扫描到一个运算符时,就把这个运算符所对应的两个子表达式移到运算符后面。(这个移动的过程我们借助栈来实现)

中缀转后缀:代码实现void infixToPostFix(char infix[],char s2[],int &top2)//第一个参数是中缀表达式串,后面两个参数是一个栈,用来保存转换之后的结果{ char s1[maxSize];int top1=-1;//辅助栈int i=0;while(infix[i] !=’\0’)//循环扫描整个中缀表达式串 { //如果是操作数则直接写出来 if(‘0’=0){if(‘0’

相关推荐: