后缀表达式（逆波兰式）、中缀表达式的转换与求值

/***********************************************************************************************************************
一、把中缀表达式转换为后缀表达式算法的基本思路是从头到尾地扫描中缀表达式中的每个字符，对于不同类型的字符按不情况进行处理。
1、先定义一个工作数组，用来存储转换之后的后缀表达式，定义一个栈，用来存储运算符。（越往栈顶优先级越高的原则）可以先定
   义一个‘#’优先级为0存入栈底
2、扫描：若遇到的是操作数，直接存入工作数组中，若遇到运算符，将该运算符与栈顶元素比较，若该运算符优先级高，直接入栈，否则，
   弹栈，直到栈顶元素优先级比该运算符优先级低，出栈后的运算符存入工作数组里。‘（’进栈时要定义低优先级，出现‘）’则弹栈。
3、扫描到中缀表达式结束符'\0'时，把栈中剩余的运算符弹出存入工作数组中。

二、计算后缀表达式的思路是：
1、从左向右扫描后缀表达式，遇到运算符就把栈顶两个元素出栈，执行运算，得到的结果再入栈.
例:(a+b)*c的逆波兰式为ab+c*，假设计算机把ab+c*按从左到右的顺序压入栈中，并且按照遇到运算符就把栈顶两个元素出栈，执行运算，
得到的结果再入栈的原则来进行处理，那么ab+c*的执行结果如下：
　　1）a入栈（0位置）
　　2）b入栈（1位置）
　　3）遇到运算符"+"，将a和b出栈，执行a+b的操作，得到结果d=a+b，再将d入栈（0位置）
　　4）c入栈（1位置）
　　5）遇到运算符"*"，将d和c出栈，执行d*c的操作，得到结果e，再将e入栈（0位置）

三、直接计算中缀表达式思路：
1、定义两个栈，一个用来存取运算符，一个用来存取操作数。
2、从左向右扫描表达式，遇到操作数，直接存入操作数栈中，遇到运算符，将该运算符与运算符栈顶元素比较，若该运算符优先级高，直接
入栈，否则弹栈，同时取操作数栈的最上面两个元素和弹出的运算符进行运算，结果压入操作数栈中。直到运算符栈顶元素优先级比该运算符
优先级低。
3、扫描完毕后，运算符依次出栈。注意：只要有一个运算符出栈，就要去操作数栈中的最上面两个元素进行计算，并把结果压入操作数栈中。
************************************************************************************************************************/

评论

3 楼 zty381309501 2011-05-14  

忘记了，如果需要计算浮点数，需要对程序修改，不仅仅是result类型。

2 楼 Touch_2011 2011-05-12  

<p><img src="/images/smiles/icon_idea.gif" alt=""></p>
<p> 运行完毕，结果正确</p>

1 楼 zty381309501 2011-05-12  

我去年在上编译原理的时候，写过逆波兰式的源码。
可以计算结果的。
以下是源码，用的思想是运算符的优先级。

我设置的结果为整形，需要的可以修改result类型。
说明一下，
1.stack是运算符堆栈，
2.'（','）'处理的过程
   遇到'（'，'（'的优先级高于所有运算符，
   遇到'）'，不入stack，而是出堆栈stack,进行计算。

#include<iostream>
using namespace std;
char simple[6]={')','+','-','/','*','('};
int stack[100];
int top=-1;
int main()
{
    char s[100];
    char t[100];
    cin>>s;
    int result[100];
	int ReTop=-1;
    int i=0,j,k=0;

	int tag=1;
cout<<"\t计算过程"<<endl;
    while(s[i]!='\0')
    {
      j=0;
      while(simple[j]!=s[i])j++;
      if(j>=6)
      {
	  t[k]=s[i];k++;
	  
	  if(tag==0)
	  {
		result[ReTop]*=10;
		result[ReTop]+=s[i]-'0';
	  }
	  else 
	  { result[++ReTop]=s[i]-'0';
	  }
	  tag=0;
	  }
	  
	  
      else
      {   t[k++]=' ';
	
         tag=1;

          if(top==-1)
          {
           top++;
		   if(j==5){stack[top]=0;}
           else stack[top]=j;
          }
          else 
          { 
           if(stack[top]<j)
            {
              top++;
              if(j==5)stack[top]=0;
              else stack[top]=j;
            }
            else 
            {
              while(top!=-1&&stack[top]>=j)
              {
               if(j==0&&stack[top]==0){break;}
               else {
				     t[k]=simple[stack[top]];
				     t[++k]=' ';
                     k++;

				     if(stack[top]==1){result[ReTop-1]+=result[ReTop];cout<<"\t{+}:="<<result[ReTop-1]<<endl;}
				     else if(stack[top]==2){result[ReTop-1]-=result[ReTop];cout<<"\t{-}:="<<result[ReTop-1]<<endl;}
				     else if(stack[top]==3){result[ReTop-1]/=result[ReTop];cout<<"\t{/}:="<<result[ReTop-1]<<endl;}
				     else if(stack[top]==4){result[ReTop-1]*=result[ReTop];cout<<"\t{*}:="<<result[ReTop-1]<<endl;}
					 ReTop--;

			   }
               top--;
              }
              
			  if(j!=0)
			  {top++;
               stack[top]=j;}
			  else top--;
            }
          }
      }
      i++;
      }
      while(top!=-1)
      {
		  t[k]=simple[stack[top]];
          t[++k]=' ';
          k++;
          
		  if(stack[top]==1){result[ReTop-1]+=result[ReTop];cout<<"\t{+}:="<<result[ReTop-1]<<endl;}
		  else if(stack[top]==2){result[ReTop-1]-=result[ReTop];cout<<"\t{-}:="<<result[ReTop-1]<<endl;}
		  else if(stack[top]==3){result[ReTop-1]/=result[ReTop];cout<<"\t{/}:="<<result[ReTop-1]<<endl;}
		  else if(stack[top]==4){result[ReTop-1]*=result[ReTop];cout<<"\t{*}:="<<result[ReTop-1]<<endl;}
		  ReTop--;
		  top--;
	  }
      t[k]='\0';
      cout<<"逆波兰式:"<<t<<endl;
      cout<<"结果："<<result[ReTop]<<" "<<endl;
      system("pause");
}