pp.cpp

我写的一个把中缀表达式转换为波兰式,并且根据波兰式求表达式值的程序.

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




int opp(char optr)
   {
   switch (optr)
   {
   case '=': return 0;
   case '(': return 1;
   case '^': return 7;
   case '*': return 5;
   case '/': return 5;
   case '%': return 5;
   case '+': return 3;
   case '-': return 3; 
   case ')': return 8;
   default: return 0;
   } 
   }//定义运算符优先级
   
  

void main()
{
stack <char> stk;
stk.push('#');//堆栈初始化
stack <char> all;//保存波兰式的所有字符包括操作符和操作数
stack <int>  opd;//保存操作数
char p[100];


cout<<"请输入原始中缀表达式:"<<endl;
cin>>p;

int l=strlen(p);
int s=0;
int e=l-1;
char temp;
while(s!=e)
{
temp=p[s];
p[s]=p[e];
p[e]=temp;
s++;
e--;
}//原表达式序列求逆

char q[100];
memset(q,0,100);
int b1=0;//p的开始
int b2=0;//q的开始
char ch;//当前字符
char y;//栈顶字符

while(b1<l)
{
ch=p[b1];
if(isdigit(ch)||isalpha(ch))
{
q[b2]=ch;
b2++;
}

else if(ch==')')
{
stk.push(ch);
}

else if(ch!='(')
{
y=stk.top();
while(y!=')'&&opp(ch)<opp(y)&&!stk.empty())
{stk.pop();

 q[b2]=y;
 y=stk.top();
 b2++;
}
stk.push(ch);
}

else if(ch=='(')
{

y=stk.top();
while(y!=')'&&!stk.empty())
{
q[b2]=y;
b2++;
stk.pop();
y=stk.top();
}
stk.pop();

}





b1++;
}

while(!stk.empty()&&stk.top()!='#')
{
    q[b2]=stk.top();
	b2++;
	stk.pop();
}
int len =strlen(q);
int m=0;
int n=len-1;
char temp1;
while(m!=n)
{
temp1=q[m];
q[m]=q[n];
q[n]=temp1;
m++;
n--;
}//原表达式序列求逆
cout<<"波兰式为:"<<endl<<q<<endl;




char ch1; 
int j=0;

while (j<len)
{
all.push(q[j]);
j++;
}

while (!all.empty())
{
 ch1=all.top();
 if (isdigit(ch1))
 {
	 int a;
	 a=atoi(&ch1);
	 opd.push(a);
	 all.pop();
 }
 else 
 {
 all.pop();
 int a=0;
 int b=0;
 int r=0;
 a=opd.top();
 opd.pop();
 b=opd.top();
 opd.pop();
switch (ch1)
{
case '+':
     r=a+b;
	 opd.push(r);
	 break;
case '-':
	r=a-b;
	 opd.push(r);
	 break;
case '*':
		r=a*b;
	 opd.push(r);
	 break;
case '/':
		r=a/b;
	 opd.push(r);
	 break;
case '%':
		r=a%b;
	 opd.push(r);
	 break;
default:
   cout<<"error"<<endl;
   break;
}

 }


}

cout<<"结果是:"<<endl<<opd.top()<<endl;
}


/*
1）求输入串的逆序。 
2）检查输入的下一元素。 
3）假如是操作数，把它添加到输出串中。 
4）假如是闭括号，将它压栈。 
5）假如是运算符，则 
i)假如栈空，此运算符入栈。 
ii)假如栈顶是闭括号，此运算符入栈。 
iii)假如它的优先级高于或等于栈顶运算符，此运算符入栈。 
iv)否则，栈顶运算符出栈并添加到输出串中，重复步骤5。 
6）假如是开括号，栈中运算符逐个出栈并输出，直到遇到闭括号。闭括号出栈并丢弃。 
7）假如输入还未完毕，跳转到步骤2。 
8）假如输入完毕，栈中剩余的所有操作符出栈并加到输出串中。 
9）求输出串的逆序。 
*/