woaidongmao

文章均收录自他人博客,但不喜标题前加-[转贴],因其丑陋,见谅!~
随笔 - 1469, 文章 - 0, 评论 - 661, 引用 - 0
数据加载中……

编译原理实验:后缀式求值(c++)

/* 将中缀表达式(a+b)转换为后缀表达式(ab+)的算法思想:  
   ·
当读到数字直接送至输出队列中  
   ·
当读到运算符t时,  
      a.
将栈中所有优先级高于或等于t的运算符弹出,送到输出队列中;    
      b.t
进栈  
   ·
读到左括号时总是将它压入栈中  
   ·
读到右括号时,将靠近栈顶的第一个左括号上面的运算符全部依次弹出,送至输出队列后,再丢弃左括号。  
  
     
运用后缀表达式进行计算的具体做法:  
   ·
建立一个栈S  
   ·
从左到右读后缀表达式,读到数字就将它转换为数值压入栈S中,读到运算符则从栈中依次弹出两个数分别到YX,然后以“X   运算符   Y”的形式计算机出结果,再压加栈S  
   ·
如果后缀表达式未读完,就重复上面过程,最后输出栈顶的数值则为结束 */

#include <iostream>
#include <string>
using namespace std;

char ex[100];//存储后缀表达式
char str[100];//
存储算术表达式
char stack[100];//
作为栈使用
char ch;//
当前判断的字符
int i=0;//i
为算术表达式str的下标
int t;//t
为后缀式ex的下标
int top=0;//top
为栈顶
void trans();//
转换函数
void compute();//
计算后缀式的值

void trans()//将中缀式转换为后缀式
{
cout<<"
输入一个算术表达式,以#号结束:"<<endl;
while(str[i]!='#')//
中缀式以#号结束
{
   i++;//
因为i的初值设为0
   cin>>str[i];
}

//
开始扫描
t=1;
i=1;
ch=str[i];
i++;//i
指向当前扫描字符的下一位
while(ch!='#')//
逐个扫描,直至遇到#号结束
{
   switch(ch)
   {
   case'('://
遇到(,进栈
    top++;
    stack[top]=ch;
    break;
   case')'://
遇到),将靠近栈顶的第一个左括号上面的运算符全部依次弹出,送至后缀式队列后,再丢弃左括号。
    while(stack[top]!='(')
    {
     ex[t]=stack[top];
     top--;
     t++;
    }
    top--;//
丢弃(
    break;
   case'+':
   case'-':
    while(top!=0 && stack[top]!='(')
    {
     ex[t]=stack[top];
     top--;
     t++;
    }
    top++;//
因为top的初值为0
    stack[top]=ch;
    break;
   case'*':
   case'/':
    while(stack[top]=='*'|| stack[top]=='/')
   {
    ex[t]=stack[top];
    top--;
    t++;
   }
   top++;
   stack[top]=ch;
   break;
 
   /*
注意!除操作数外,其它符号都要用到栈*/
   default:while(ch>='0' && ch<='9')//
遇到操作数直接送至后缀式队列
     {
      ex[t]=ch;
      t++;
      ch=str[i];
      i++;//
此时i指向操作数之后的运算符的后一位!!
     }
    i--;//
要在操作数之后,运算符之前添加空格符
    ex[t]=' ';//
用空格符隔开
    t++;

   }//switch结束

   ch=str[i];//仿照default中的,返回添加空格符之前的操作
   i++;
}//
结束while


while(top!=0)//
仍有运算符在栈中
{
   ex[t]=stack[top];
   t++;
   top--;
}
ex[t]=' ';//
不能省,若省掉则无法进入compute函数??

for(int j=1;j<i-1;j++)
   cout<<str[j];
cout<<"
的后缀式为:";
for(j=1;j<t;j++)
cout<<ex[j];

}

void compute()
{
float stack[100];//
作为栈使用
int d;//
用于存放当前的计算结果
char ch;
int t=1;
int top =0;
ch=ex[t];
t++;

while(ch!=' ')//此空格符为后缀式中的最后一个字符,与上文中的" ex[t]=' '; "相对应
{
   switch(ch)
   {
   case'+':
    stack[top-1]=stack[top-1]+stack[top];
    top--;
    break;
   case'-':
    stack[top-1]=stack[top-1]-stack[top];
    top--;
    break;
   case'*':
    stack[top-1]=stack[top-1]*stack[top];
    top--;
    break;
   case'/':
    if(stack[top]!=0)
     stack[top-1]=stack[top-1]/stack[top];
    else
    {
     cout<<"\n
除零错误!"<<endl;
     exit(0);//
异常退出
    }
    top--;//
两个操作数算出一个结果存放到栈顶,那两操作数便可丢弃,故top-1
    break;
   default:
    d=0;
    while(ch>='0' && ch<='9')
    {
     d=10*d+ch-'0';//
将数字字符转化为对应的数值,*10是与大于10的数值时要进位
     ch=ex[t];
     t++;
    }
    top++;
    stack[top]=d;//
栈顶存放当前计算结果
 
   }//switch
结束
   ch=ex[t];//
跳过空格符,扫描下一个运算符或操作数
   t++;
}
cout<<"\n
计算结果为:"<<stack[top]<<endl;
}

void main()
{
trans();
compute();
}

结果如图所示:

clip_image001

 

posted on 2010-03-05 16:15 肥仔 阅读(874) 评论(0)  编辑 收藏 引用 所属分类: 状态机 & 自动机 & 形式语言


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理