利用堆栈解析算术表达式一:基本过程1 本文目标
大致的规律是,一元运算符 > 二元运算符 > 多元运算符。 4 利用堆栈解析算术表达式的过程 中缀表达式翻译成后缀表达式的方法如下: (1)从右向左依次取得数据ch。 (2)如果ch是操作数,直接输出。 (3)如果ch是运算符(含左右括号),则: a:如果ch = '(',放入堆栈。 b:如果ch = ')',依次输出堆栈中的运算符,直到遇到'('为止。 c:如果ch不是')'或者'(',那么就和堆栈顶点位置的运算符top做优先级比较。 1:如果ch优先级比top高,那么将ch放入堆栈。 2:如果ch优先级低于或者等于top,那么输出top,然后将ch放入堆栈。 (4)如果表达式已经读取完成,而堆栈中还有运算符时,依次由顶端输出。 如果我们有表达式(A-B)*C+D-E/F,要翻译成后缀表达式,并且把后缀表达式存储在一个名叫output的字符串中,可以用下面的步骤。 (1)读取'(',压入堆栈,output为空 (2)读取A,是运算数,直接输出到output字符串,output = A (3)读取'-',此时栈里面只有一个'(',因此将'-'压入栈,output = A (4)读取B,是运算数,直接输出到output字符串,output = AB (5)读取')',这时候依次输出栈里面的运算符'-',然后就是'(',直接弹出,output = AB- (6)读取'*',是运算符,由于此时栈为空,因此直接压入栈,output = AB- (7)读取C,是运算数,直接输出到output字符串,output = AB-C (8)读取'+',是运算符,它的优先级比'*'低,那么弹出'*',压入'+",output = AB-C* (9)读取D,是运算数,直接输出到output字符串,output = AB-C*D (10)读取'-',是运算符,和'+'的优先级一样,因此弹出'+',然后压入'-',output = AB-C*D+ (11)读取E,是运算数,直接输出到output字符串,output = AB-C*D+E (12)读取'/',是运算符,比'-'的优先级高,因此压入栈,output = AB-C*D+E (13)读取F,是运算数,直接输出到output字符串,output = AB-C*D+EF (14)原始字符串已经读取完毕,将栈里面剩余的运算符依次弹出,output = AB-C*D+EF/- 5 计算算术表达式 当有了后缀表达式以后,运算表达式的值就非常容易了。可以按照下面的流程来计算。 (1)从左向右扫描表达式,一个取出一个数据data (2)如果data是操作数,就压入堆栈 (3)如果data是操作符,就从堆栈中弹出此操作符需要用到的数据的个数,进行运算,然后把结果压入堆栈 (4)如果数据处理完毕,堆栈中最后剩余的数据就是最终结果。 比如我们要处理一个后缀表达式1234+*+65/-,那么具体的步骤如下。 (1)首先1,2,3,4都是操作数,将它们都压入堆栈 (2)取得'+',为运算符,弹出数据3,4,得到结果7,然后将7压入堆栈 (3)取得'*',为运算符,弹出数据7,2,得到数据14,然后将14压入堆栈 (4)取得'+',为运算符,弹出数据14,1,得到结果15,然后将15压入堆栈 (5)6,5都是数据,都压入堆栈 (6)取得'/',为运算符,弹出数据6,5,得到结果1.2,然后将1.2压入堆栈 (7)取得'-',为运算符,弹出数据15,1.2,得到数据13.8,这就是最后的运算结果 6 示例代码 /// <summary>
/// 将中缀表达式翻译成后缀表达式 /// 输入中缀表达式: A+B*(C+D)-E/F /// 翻译成后缀表达式:ABCD+*+EF/- /// 中缀表达式翻译成后缀表达式的方法如下: /// (1)从左向右依次取得数据ch /// (2)如果ch是操作数,直接输出 /// (3)如果ch是运算符(含左右括号),则: /// a:如果ch = '(',放入堆栈 /// b:如果ch = ')',依次输出堆栈中的运算符,直到遇到'('为止 /// c:如果ch不是')'或者'(',那么就和堆栈顶点位置的运算符top做优先级比较 /// 1:如果ch优先级比top高,那么将ch放入堆栈 /// 2:如果ch优先级低于或者等于top,那么输出top,然后将ch放入堆栈 /// (4)如果表达式已经读取完成,而堆栈中还有运算符时,依次由顶端输出 /* Pseudocode() { n = passing(s, op); //s是表达式,op是数据数组,n是数据的数量 for(int i=0; i<n; i++) { ch = op(i); if(ch是操作数) output(ch); else { if(ch == '(') push(ch); else if( ch == ')') pop()而且输出,直到遇到'('为止; else { if(运算符ch较stack[top]优先) push(ch); else { pop()且输出; push(ch); } } } } */ /// </summary> public class PosfixParser { private static string expression = "1+4/(1+1)+2*(3+4)-6/3+5/(1/2+2/1)"; private static Stack myStack = new Stack(); private static StringBuilder posfixExpression = new StringBuilder(); public static void Main() { Console.WriteLine("This Midfix expression is: {0}", expression); Console.WriteLine("The Posfix expression is: {0}", Parse()); Console.WriteLine("The result is {0}", Calculate()); Console.Read(); } //将中缀表达式解析成后缀表达式 public static string Parse() { int i, j = 0; char ch, ch1; char[] A = expression.ToCharArray(); //将字符串转成字符数组,要注意的是,不能有大于10的数存在 char[] B = new char[A.Length]; //最后生成的后缀表达式会小于这个长度,因为有括号 int length = A.Length; for(i=0; i<length; i++) { ch = A[i]; if( IsOperand( ch ) ) //如果是操作数,直接放入B中 { B[j++] = ch; } else { if( ch == '(' ) //如果是'(',将它放入堆栈中 myStack.Push(ch); else if( ch == ')') //如果是')' { while( !IsEmpty(myStack) ) //不停地弹出堆栈中的内容,直到遇到'(' { ch = (char)myStack.Pop(); if( ch == '(' ) break; else B[j++] = ch; //将堆栈中弹出的内容放入B中 } } else //既不是'(',也不是')',是其它操作符,比如+, -, *, /之类的 { if( !IsEmpty( myStack ) ) { do { ch1 = (char)myStack.Pop();//弹出栈顶元素 if(Priority(ch) > Priority(ch1)) //如果栈顶元素的优先级小于读取到的操作符 { myStack.Push(ch1);//将栈顶元素放回堆栈 myStack.Push(ch);//将读取到的操作符放回堆栈 break; } else//如果栈顶元素的优先级比较高或者两者相等时 { B[j++] = ch1; //将栈顶元素弹出,放入B中 if( IsEmpty(myStack) ) { myStack.Push(ch); //将读取到的操作符压入堆栈中 break; } } } while( !IsEmpty(myStack)); } else //如果堆栈为空,就把操作符放入堆栈中 { myStack.Push(ch); } } } } while( !IsEmpty(myStack ) ) B[j++] = (char)myStack.Pop();//将堆栈中剩下的操作符输出到B中 for(i=0; i<B.Length; i++) if( B[i] != '\0' ) //去除多余的空字符 posfixExpression.Append(B[i]); return posfixExpression.ToString(); } //计算后缀表达式的值 public static double Calculate() { int i; double no1, no2, ret; char ch; char[] A = posfixExpression.ToString().ToCharArray(); myStack.Clear(); for(i=0; i<A.Length; i++) { ch = A[i]; if(IsOperand(ch))//如果是操作数,直接压入栈 { myStack.Push((double)(ch-48)); } else //如果是操作符,就弹出两个数字来进行运算 { no1 = (double) myStack.Pop(); no2 = (double) myStack.Pop(); ret = GetValue(ch, no1, no2); myStack.Push(ret);//将结果压入栈 } } return (double)myStack.Pop();//弹出最后的运算结果 } //对两个值利用运算符计算结果 private static double GetValue(char op, double ch1, double ch2) { switch( op ) { case '+': return ch2 + ch1; case '-': return ch2 - ch1; case '*': return ch2 * ch1; case '/': return ch2 / ch1; default: return 0; } } //判断堆栈是否为空 private static bool IsEmpty(Stack st) { return st.Count == 0 ? true: false; } //判断是否是操作数 private static bool IsOperand( char ch ) { char[] operators = { '+', '-', '*', '/', '(', ')' }; for(int i=0; i<operators.Length; i++) if( ch == operators[i] ) return false; return true; } //返回运算符的优先级 private static int Priority( char ch ) { int priority; switch( ch ) { case '+' : priority = 1; break; case '-' : priority = 1; break; case '*' : priority = 2; break; case '/' : priority = 2; break; default : priority = 0; break; } return priority; } } 利用上述程序可以求解只包含+,-,*,/,()和0-9之间的数字的表达式的值。这只是一个相当初级的程序,还有很多工作没有完成,但是只要我们弄清楚了其中的过程和步骤,剩下的工作就不再是那么困难了。 |
|