ch5_2(表达式求值问题)

2018/1/12,数据结构,1,1,栈的应用 表达式的求解,任何一个表达式均是由操作数Operand、运算符Operator和界限符Delimiter组成。为了叙述简洁，在此只讨论二元运算符构成的算术表达式。假设，表达式Exp = (第一操作数)S1 OP (第二操作数)S2，即Exp = S1 OP S2。其中S1和S2可以是简单变量也可以是表达式。,2018/1/12,数据结构,2,2,算术表达式算符之间的优先级关系,2018/1/12,数据结构,3,3,算术表达式求解的过程, 初始化两个栈：符号栈OP和操作数栈S，其中S初始化为空，将结束符“#”首先压入栈OP。 从左向右开始扫描算术表达式，用1表示栈OP的栈顶算符，2表示刚刚扫描到的算符，用val(i)表示算符i的优先级。,2018/1/12,数据结构,4,4,do if 扫描到的是操作数 将其压入栈S；继续扫描； else if(val(2) val(1) 将扫描到的2压入栈OP；继续扫描； else if(val(2) ab+ a+(b-c) -abc-+ a+(b-c)*d -abc-d*+ a+d*(b-c)-adbc-*+,2018/1/12,数据结构,8,8,编写一个函数将一般表达式转化为逆波兰表达式。解：假设表达式中的符号以字符形式由键盘输入（为简单起见，设算术表达式中的参加运算的数都只有一位数字），该算术表达式存放在字符型数组str中，其逆波兰表达式依次存放在字符型数组exp中，在处理函数中用一个字符型数组stack作为栈。设字符“#”为表达式的终止符，将算术表达式转换成逆波兰表示的方法如下：依次从键盘输入表达式中的字符c，对于每一个c：若c为数字，则将c依次存入数组exp中；若c为左括弧“（”，则将此括弧压入栈stack；若c为右括弧“）”，则将栈stack中的左括弧“（”以前的字符依次弹出存入数组exp中，然后将左括弧“（”弹出；若c为“+”或“-”，则将当前栈stacl中“（”以前的所有字符（运算符）依次弹出存入数组exp中，然后将c压入栈stack中；若c为“*”或“/”，则将当前栈stack中的栈顶端的“*”或“/”弹出并依次存入数组exp中，然后将c压入栈stack中；若c为“#”,则将栈stack中的所有运算符依次弹出并存入数组exp中，然后再将c存入数组exp中，最后可得到表达式的逆波兰表示在数组exp中。,2018/1/12,数据结构,9,9,viod trans()char strmaxsize;char expmaxsize; char stackmaxsize;char ch;int i,j,t,top=0;i=0;doi+; scanf(“%c”,stri);while(stri!=#,2018/1/12,数据结构,10,10,逆波兰表达式的优势它的优势在于只用两种简单操作，入栈和出栈就可以搞定任何普通表达式的运算。其运算方式如下： 如果当前字符为变量或者为数字，则压栈，如果是运算符，则将栈顶两个元素弹出作相应