postfix.cpp

利用堆栈进行表达式的 Infix -> postfix 转换 适合大专院校计算机专业数据结构课参考 用法： 输入infix表达式为：(3+2*3)^2 则 转换位postfix表达式

#include <iostream.h>
#include <conio.h>
#include <stdio.h>
#include <string.h>
#include <math.h>

char oper[2][100]={{'+','-','*','/','^'},
                   {1,  1,  2,  2,  3 }};

class STACK
{
int a[100];
int top;
public:
STACK()
   {top=-1;}
void push(char c)
   {top++; a[top]=c;}
int isempty()
   {
   if(top==-1) {return 1;}
   else {return 0;}
   }
int pop()
   {
    if(isempty()) {return 0;}
    top--;
    return a[top+1];
   }
int gettop()
   {
    if(isempty()) {return 0;}
    return a[top];
   }
};

class POSTFIX
{
char infixstr[100];
char postfixstr[100];
STACK s1;
public:
void setinfix(char *str)
   {strcpy(infixstr,str);}
char *getpostfix()
   {return postfixstr;}
int isoperand(int op)
   {
   if((op>='0')&&(op<='9') || (op>='a')&&(op<='z') || (op>='A')&&(op<='Z') )
      {return 1;}
   else
      {return 0;}
   }
int prcd(int op1,int op2)
   {
    int i,pri1=0,pri2=0;
    if ((op1=='(')||(op2=='(')) {return 0;}
    if (op2==')') {return 1;}
    for(i=0;i<100;i++)
       {
	 if(oper[0][i]==op1) pri1=oper[1][i];
	 if(oper[0][i]==op2) pri2=oper[1][i];
       }
    if(pri1>=pri2) {return 1;}
    else {return 0;}
   }
void transfer()
   {
   int pos,outpos=0;
   int symb,topsymb;
   for(pos=0; symb=infixstr[pos] ; pos++ )
      {
       if(isoperand(symb))
	  {postfixstr[outpos++]=symb;}
       else
	  {
	  if(!s1.isempty())
	      {
	      topsymb=s1.pop();
	      if(symb==')')
		{
		while(topsymb!='(')
		  {postfixstr[outpos++]=topsymb; topsymb=s1.pop();}
		}
	      else
		{
		s1.push(topsymb);
		while (!s1.isempty() && prcd(topsymb=s1.gettop(),symb))
		   {postfixstr[outpos++]=topsymb; topsymb=s1.pop(); }
		}
	      }
	  if(symb!=')') s1.push(symb);
	  }
      }
   while(!s1.isempty())
     {
	topsymb=s1.pop();
	postfixstr[outpos++]=topsymb;
      }
   postfixstr[outpos++]='\0';
   }
};

class EVAL
{
char postfixstr[100];
int result;
STACK s1;
public:
void setpostfix(char *str)
   {strcpy(postfixstr,str);}
int getans()
   {return result;}
int isins(int op)
   {
   int i,flag=0;
   for(i=0;i<100;i++)
      if(op==oper[0][i]) {flag=1; break;}
   return flag;
   }
void calc()
   {
   int a1,a2,s,pos,symb;
   char str[100];
   strcpy(str,postfixstr);
   for(pos=0; str[pos]!='\0'; pos++ )
     if(!isins(str[pos])) str[pos]-='0';
   for(pos=0; str[pos]!='\0'; pos++ )
      {
      symb=str[pos];
      if(!isins(symb))
	 { s1.push(symb); }
      else
	{
	a2=s1.pop();
	a1=s1.pop();
	if(symb=='+') s=a1+a2;
	if(symb=='-') s=a1-a2;
	if(symb=='*') s=a1*a2;
	if(symb=='/') s=a1/a2;
	if(symb=='^') s=pow(a1,a2);
	s1.push(s);
	}
      }
   result=s1.pop();
   }
};

void main()
{
POSTFIX post1;
EVAL e1;
char key,str[100];
clrscr();
cout<<"Tip: you can input + - * / ^ ( ) 0-9 a-z";
cout<<"\n\nEnter infix string: ";
gets(str);
post1.setinfix(str);
post1.transfer();
cout<<"\n\nPostfix: "<<post1.getpostfix()<<"\n";
cout<<"\n\nDo you want to evaluation?(y/n) ";
key=getch(); putch(key);
if(key=='Y' || key=='y')
  {
  e1.setpostfix(post1.getpostfix());
  e1.calc();
  cout<<"\n\n"<<str<<" = "<<e1.getans();
  }
cout<<"\n\nPress any key to return...";
getch();
}