公式的评价问题1 .将骑马订式和后缀式介绍给双眼运算。 我们平时写的公式是x*y一样的形式，那个运算符介于两个运算符之间，这个公式叫做骑马订公式。 在计算此表达式时，必须注意运算符的优先级，在某些情况下，需要使用括号来准确表示运算顺序。 也就是说，如果运算符的实际顺序经常与表达式的优先级不匹配，这种格式的表达式对我们来说很容易理解，但在计算机上计算骑马订表达式的值很复杂。 因此，提出了一种后缀表达式——逆波兰表达式。
什么是逆波兰式？ 逆波兰表达式是在逆波兰表达式中，所有运算符都位于操作数之后的公式。 另外，逆波兰表示法不需要括号来识别操作员的优先顺序。 (简单地说，反波兰表达式是将运算符放在操作数之后，不带括号。)
例如：
骑马订式ab为后缀式： ab*
骑马订式(a b ) ****c写成后缀式(ab c )
骑马订式(a b ) ) c-(a b )/e为后缀式) ab c*****ab e/-
2 .用后缀表达式评价算法随后添加
3 .直接使用骑马订公式评价算法面临问题：
1 .决定运算符的优先顺序(相邻两个运算符的优先顺序关系) ) ) ) ) )。
2 .判断当前处理的字符是运算符还是操作数
3 .每个运算符的运算顺序由后面的运算符决定
下面是运算符优先级表
op1/op 2http://www.Sina.com/http://www.Sina.com/* * * http://www.Sina.com/http://www.com
(1)算法的想法1 )设置操作数堆栈和运算符堆栈
2 .公式的结尾为’ n’，默认运算符堆栈的堆栈底为’ n’
3 .当前字符为操作数时，直接按操作数堆栈
4如果当前字符是运算符，并且运算符的优先级高于堆栈顶部运算符，则进入堆栈。 否则，从运算符类型中调用两个操作数运算符堆栈的堆栈顶部运算符，并将计算结果推入操作数堆栈
(2) )代码实现) /表达式评估问题) /作者：清新阿里(/时间： 2020年10月18日# include stdio.h # include malloc.h # define stack _ size 30 typedio }SeqStack； //堆栈初始化voidinitstack(seqstack*s ) {S-top=-1； //堆栈已满intisfull(seqstacks ) if ) s.top==stack_size-1 ) return 1； elsereturn 0； //堆栈为空的intisempty(seqstacks ) if ) s.top==-1 ) return 1； elsereturn 0； //堆栈intpush(seqstack*s，char x ) if (is full ) s ) ) return 0； else {s-top； s-elem[s-top]=x； 返回1； }//intpop(seqstack*s，char* x ) if (isempty ) s ) ) return 0； else{*x=s-elem[s-top]； s-top----； 返回1； }//获得当前运算符intgettop(seqstacks ) return (s.elem [ s.top ] )； //运算符集合intisopr(charch ) switch ) {case' ':return 1； 布雷克； case '-' :返回1； 布雷克； case ' * ' :返回1； 布雷克； case '/' :返回1； 布雷克； case ' (:返回1； 布雷克； case ' ) ' :返回1； 布雷克； case'n':return 1； 布雷克； default :返回0； }//voidcalulate(seqstack*oprd，char x ) {char elem_1； char elem_2； char elem； pop () oprd )、elem_2)； pop () oprd )、elem_1)； sitch(x ) case'':elem=(char ) ) ) ) ) ) ) ) )。
(((int)(elem_1 - '0') + (int)(elem_2 - '0')) + '0');Push(&(*OPRD), elem);break;case'-':elem = (char)(((int)(elem_1 - '0') - (int)(elem_2 - '0')) + '0');Push(&(*OPRD), elem);break;case'*':elem = (char)(((int)(elem_1 - '0') * (int)(elem_2 - '0')) + '0');Push(&(*OPRD), elem);break;case'/':elem = (char)(((int)(elem_1 - '0') / (int)(elem_2 - '0')) + '0');Push(&(*OPRD), elem);break;}}char compare(char current_ch,char ch){//输入的运算符比当前栈中的优先级高if ((current_ch == 'n' && (ch == '+' || ch == '-' || ch == '*' || ch == '/'||ch=='(')) || (current_ch == '+' && (ch == '*' || ch == '/'||ch == '(')) ||(current_ch == '-' && (ch == '*' || ch == '/'||ch == '('))||(current_ch=='('&&(ch == '+' || ch == '-' || ch == '*' || ch == '/'))||(current_ch=='*'&&(ch=='('))||(current_ch=='/'&&ch=='('))return '>';//输入的运算符比当前栈中的优先级低else if ((current_ch == '+' && (ch == '+' || ch == '-' || ch == 'n'||ch==')')) || (current_ch == '-' && (ch == '+' || ch == '-' || ch == 'n' || ch == ')')) ||(current_ch == '*' && (ch == '*' || ch == '/' || ch == 'n' || ch == '+' || ch == '-' || ch == ')')) ||(current_ch == '/' && (ch == '*' || ch == '/' || ch == 'n' || ch == '+' || ch == '-' || ch == ')'))||(current_ch=='('&&ch==')'))return '<';}//计算表达式void CalExpression(){SeqStack OPRD;//OPRD为操作数SeqStack OPTR;//OPTR为运算符char x;char y;InitStack(&OPRD);InitStack(&OPTR);Push(&OPTR,'n');printf("请输入表达式：n");char ch = getchar();while (ch != 'n' || GetTop(OPTR) != 'n'){if (!IsOpr(ch))//判断字符是否为操作数{Push(&OPRD, ch);//将操作数进栈ch = getchar();}else if (IsOpr(ch))switch (compare(GetTop(OPTR), ch)){case'>':Push(&OPTR, ch);ch = getchar();break;case'<':Pop(&OPTR, &x);//printf("运算符为：%cn", x);//printf("运算符的数组序号：%dn", OPTR.top);if(x!='(')Calulate(&OPRD, x);else if (x == '(') ch = getchar();if (ch != 'n'&&ch!=')'){if (compare(GetTop(OPTR), ch) == '>'){Push(&OPTR, ch);ch = getchar();}else if (compare(GetTop(OPTR), ch)){Pop(&OPTR, &x);Calulate(&OPRD, x);Push(&OPTR, ch);ch = getchar();}}else if (ch == 'n'||ch==')')break;}}Pop(&OPRD, &y);printf("表达式的值为：%dn", (int)(y - '0'));}int main(){CalExpression();return 0;} （3）运行结果： （4）算法缺点：该算法只能只能实现0-9之间简单的算数运算，不能实现多位数之间的简单运算
（5）算法优化：待优化
4.算术表达式二叉树对于算术表达式(2-3)*(4+5)，将其组织成二叉树看起来是这样：
先序遍历: * - 2 3 + 4 5中序遍历: 2 - 3 * 4 + 5后序遍历: 2 3 - 4 5 + *以上的二叉树称之为表达式二叉树。表达式二叉树有些特性，所有的叶子节点都是操作数，所有的非叶子节点都是操作符。这很容易理解，在基本计算单元中，操作符是核心，同时计算结果是另一个基本计算单元的操作数，反映到二叉树中，操作符既是子树的根节点同时也是另一颗子树的子节点，那就是非叶子节点。
算数表达式二叉树
按照先加减后乘除的原则构造二叉树
算数表达式二叉树的特点
数字只能是叶子节点, 且叶子节点只能是数字
+、- 符号永远只能祖宗节点或者左孩子节点
如果遇到 * 、/ 则 将其作为祖宗节点来看, 其右孩子节点只能是 数字, 左孩子节点是 * / 符号或者 数字
如果将算术表达式用表达式二叉树组织，表达式二叉树的先序遍历结果就是先缀表达式。同理，中序遍历是中缀表达式，后序遍历是后缀表达式。但是，这里有个缺陷，中序遍历结果是没有考虑优先级以及括号的，所以结果是有歧义的。不过这不是问题，我们可以通过判断来添加括号。
如果有以下中缀表达式：
(2-3)*(4+5)
为了快速求取先缀以及后缀表达式，我们首先把括号补全，变成下面这样：
((2-3)*(4+5))
然后把所有操作符放在它所对应的左括号的前面，就是这样：
*(-(2 3)+(4 5))
最后把括号去掉，变成这样：
*** - 2 3 + 4 5**
这就是先缀表达式，同理可以获取后缀表达式。
通过以上方式，我们完全可以心算出先缀以及后缀表达式，非常方便。