接尾辞式を接尾辞式に変換して評価する(C++スタックの適用)

11955 ワード

/*
* biao.cpp
*
* Created on: 2011-11-25
* Author: allenjin
*/

#include<iostream>
#include<string.h>
using namespace std;
template<class T>
class Stack{ //
public: Stack(){Top=0;}
T top(){return a[Top];}
void pop(){Top--;}
bool isempty(){
if(Top==0)return true;
else return false;}
void push(T b)
{
Top++;
a[Top]=b;}
private:
T a[100];int Top;
};
void chpost(char inorder[],char post[],int& m)// , m
{
int n=strlen(inorder);//
Stack<char> czf;// char ;
for(int i=0;i<n;i++)
{
if(inorder[i]>='0'&&inorder[i]<='9')//
{
post[m]=inorder[i];
m++;
}
if(inorder[i]=='(')czf.push(inorder[i]);// ‘(’
if(inorder[i]=='+')// ‘+’ , , ‘+’
{
if(!czf.isempty()&&(czf.top()=='*'||czf.top()=='/'||czf.top()=='-'))
{ post[m++]=czf.top();czf.pop();czf.push(inorder[i]);}
else{czf.push(inorder[i]);}
}
if(inorder[i]=='-')// ‘-’ , , ‘-’
{
if(!czf.isempty()&&(czf.top()=='*'||czf.top()=='/'))
{
post[m++]=czf.top();czf.pop();czf.push(inorder[i]);
}else{czf.push(inorder[i]);}
}
if(inorder[i]=='*'||inorder[i]=='/')czf.push(inorder[i]);// ‘*’ ‘/’
if(inorder[i]==')')// ‘)’ ‘(’
{
while(czf.top()!='(')
{post[m++]=czf.top();czf.pop();}
czf.pop();// ‘(’
}
}
while(!czf.isempty())//
{post[m++]=czf.top();czf.pop();}
}
int yusuan(char post[],int n)//
{
Stack<int>ss;// int
int a,b,c,result;
for(int i=0;i<n;i++)
{
if(post[i]>='0'&&post[i]<='9')
{
ss.push((post[i]-'0'));// char int
}

if(post[i]=='-')
{
b=ss.top();ss.pop();a=ss.top();ss.pop();
c=a-b;ss.push(c);
}
if(post[i]=='+')
{
b=ss.top();ss.pop();a=ss.top();ss.pop();
c=a+b;ss.push(c);
}
if(post[i]=='*')
{
b=ss.top();ss.pop();a=ss.top();ss.pop();
c=a*b;ss.push(c);
}
if(post[i]=='/')
{
b=ss.top();ss.pop();a=ss.top();ss.pop();
c=a/b;ss.push(c);
}
}
result=ss.top();//
ss.pop();//
return result;
}
int main(void)
{

char in[100];char a;int i=0;
cout<<" (# ):";
while(cin>>a)// ‘#’
{
if(a=='#')break;
in[i++]=a;
}
char po[100];int n=0;
chpost(in,po,n);
cout<<" :";
for(int j=0;j<n;j++)cout<<po[j]<<"";
cout<<endl;
cout<<" :"<<yusuan(po,n)<<endl;
return 0;
}