前缀表达式
什么是前缀表达式
前缀表达式如何求值
前缀表达式有什么用处
中缀表达式转换为前缀表达式的一些例子
中缀表达式转换为前缀表达式的一般算法
实例分析
各运算符及符号优先级
用编程实现中缀表达式向前缀表达式的转换
编辑本段
什么是前缀表达式
  前缀表达式就是不含括号的算术表达式，而且它是将运算符写在前面，操作数写在后面的表达式，也称为“波兰式”。例如，- 1 + 2 3，它等价于1-(2+3)。
编辑本段
前缀表达式如何求值
  对于一个前缀表达式的求值而言，首先要从右至左扫描表达式，从右边第一个字符开始判断，如果当前字符是数字则一直到数字串的末尾再记录下来，如果是运算符，则将右边离得最近的两个“数字串”作相应的运算，以此作为一个新的“数字串”并记录下来。一直扫描到表达式的最左端时，最后运算的值也就是表达式的值。例如，前缀表达式“- 1 + 2 3“的求值，扫描到3时，记录下这个数字串，扫描到2时，记录下这个数字串，当扫描到+时，将+右移做相邻两数字串的运算符，记为2+3，结果为5，记录下这个新数字串，并继续向左扫描，扫描到1时，记录下这个数字串，扫描到-时，将-右移做相邻两数字串的运算符，记为1-5，结果为-4，所以表达式的值为-4。
编辑本段
前缀表达式有什么用处
  前缀表达式是一种十分有用的表达式，它将中缀表达式转换为可以依靠简单的操作就能得到运算结果的表达式。例如，(a+b)*(c+d)转换为*,+,a,b,+,c,d。它的优势在于只用两种简单的操作，入栈和出栈就可以解决任何中缀表达式的运算。其运算方式为：如果当前字符(或字符串)为数字或变量，则压入栈内；如果是运算符，则将栈顶两个元素弹出栈外并作相应运算，再将结果压入栈内。当前缀表达式扫描结束时，栈里的就是中缀表达式运算的最终结果。
编辑本段
中缀表达式转换为前缀表达式的一些例子
  a+b ---> +,a,b 
  a+(b-c) ---> +,a,-,b,c 
  a+(b-c)*d ---> +,a,*,-,b,c,d 
  a=1+3 ---> a=+,1,3
编辑本段
中缀表达式转换为前缀表达式的一般算法
  (1) 首先构造一个运算符栈(也可放置括号)，运算符(以括号分界点)在栈内遵循越往栈顶优先级不降低的原则进行排列。 
  (2)从右至左扫描中缀表达式，从右边第一个字符开始判断： 
  如果当前字符是数字，则分析到数字串的结尾并将数字串直接输出。 
  如果是运算符，则比较优先级。如果当前运算符的优先级大于等于栈顶运算符的优先级(当栈顶是括号时，直接入栈)，则将运算符直接入栈；否则将栈顶运算符出栈并输出，直到当前运算符的优先级大于等于栈顶运算符的优先级(当栈顶是括号时，直接入栈)，再将当前运算符入栈。 
  如果是括号，则根据括号的方向进行处理。如果是右括号，则直接入栈；否则，遇右括号前将所有的运算符全部出栈并输出，遇右括号后将左右的两括号一起删除。 
  (3) 重复上述操作(2)直至扫描结束，将栈内剩余运算符全部出栈并输出，再逆序输出字符串。中缀表达式也就转换为前缀表达式了。
编辑本段
实例分析
  将中缀表达式“1+((2+3)*4)-5”转换为前缀表达式。 
  中缀表达式 后缀表达式 运算符栈 说明 
  5 5 空 5，是数字串直接输出 
  - 5 - -，栈内无运算符，直接入栈 
  ) 5 - ) )，直接入栈 
  4 5 4 - ) 4，是数字串直接输出 
  * 5 4 - ) * *，栈顶是括号，直接入栈 
  ) 5 4 - ) * ) )，直接入栈 
  3 5 4 3 - ) * ) 3，是数字串直接输出 
  + 5 4 3 - ) * ) + +，栈顶是括号，直接入栈
  2 5 4 3 2 - ) * ) + 2，是数字串直接输出 
  ( 5 4 3 2 + - ) * (，参考① 
  ( 5 4 3 2 + * - (，参考① 
  + 5 4 3 2 + * - + +，优先级大于等于栈顶运算符，直接入栈 
  1 5 4 3 2 + * 1 - + 1，是数字串直接输出
  空 5 4 3 2 + * 1 + - 空 描扫结束，将栈内剩余运算符全部出栈并输出　空 - + 1 * + 2 3 4 5 空 逆序输出字符串
编辑本段
各运算符及符号优先级
  )：直接入栈 
  (：遇)前，将运算符全部出栈并输出；遇)后，将两括号一起删除 ①
  +、-：1 
  *、/、%：2 
  ^：3
编辑本段
用编程实现中缀表达式向前缀表达式的转换
  #include<stdio.h>
  #include<conio.h>
  #include<math.h>
  #include<string.h>
  #define MaxSize 99
  char calc[MaxSize],expr[MaxSize];
  int i,t;
  struct
  { printf直接输出数字
  char data[MaxSize];
  int top;
  }Sym;
  struct
  {
  double data[MaxSize];
  int top;
  }Num;
  double ston(char x[],int *p)
  {
  int j=*p-1,i;
  double n=0,m=0;
  while(x[j]>='0'&&x[j]<='9')
  {
  j--;
  }
  if(x[j]!='.')
  {
  for(i=j+1;i<=*p;i++)
  {
  n=10*n+(x[i]-'0');
  }
  }
  else
  {

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。