T9的空间

You will never walk alone!

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  69 随笔 :: 0 文章 :: 28 评论 :: 0 Trackbacks
今天做了个题,主要就是判断两个算术表达式是否相等,当然是用栈了,先将表达式转化为后缀表达式,然后栈求值
  1/*Source Code
  2
  3Problem: 1686  User: Torres 
  4Memory: 224K  Time: 0MS 
  5Language: C++  Result: Accepted 
  6
  7Source Code */

  8#include<iostream>
  9#include<string>
 10#include<stack>
 11#include<map>
 12using namespace std;
 13
 14map<char,int>mp;
 15
 16bool isletter(char &c)
 17{
 18    if(c>='a'&&c<='z'||c>='A'&&c<='Z'||c>='1'&&c<='9')
 19        return true;
 20    else return false;
 21}

 22
 23string change(char str[])
 24{
 25    int i,j;
 26    int len=strlen(str);
 27    string temp;
 28    char ch[200];
 29    stack<char> cs;
 30    for(i=0,j=0;i<len;i++)
 31        if(isletter(str[i]))ch[j++]=str[i];
 32        else{
 33            switch(str[i]){
 34            case '(':cs.push(str[i]);break;
 35            case ')':
 36                while(cs.top()!='('){
 37                    ch[j++]=cs.top();
 38                    cs.pop();
 39                }

 40                cs.pop();
 41                break;
 42            case '+':
 43            case '-':
 44            case '*':
 45                while(!cs.empty()&&mp[str[i]]<=mp[cs.top()]){
 46                    ch[j++]=cs.top();
 47                    cs.pop();
 48                }

 49                cs.push(str[i]);
 50                break;
 51            }

 52        }

 53    while(!cs.empty())ch[j++]=cs.top(),cs.pop();
 54    ch[j]='\0';
 55    temp=ch;
 56    return temp;
 57}

 58
 59int result(string &str)
 60{
 61    int i;
 62    int len=str.size();
 63    stack<int> re;
 64    for(i=0;i<len;i++)
 65        if(isletter(str[i]))
 66        {
 67            if(str[i]>='1'&&str[i]<='9')
 68                re.push(str[i]-'0');
 69            else 
 70                re.push((int)str[i]);
 71        }

 72        else{
 73            int a,anext,b;
 74            a=re.top();
 75            re.pop();
 76            anext=re.top();
 77            re.pop();
 78            switch(str[i]){
 79                case'+':b=a+anext;re.push(b);break;
 80                case'-':b=anext-a;re.push(b);break;
 81                case'*':b=a*anext;re.push(b);break;
 82            }

 83        }

 84    return re.top();
 85}
    
 86
 87int main()
 88{
 89    int N,ca;
 90    char str1[100],str2[100];
 91    mp['+']=1;
 92    mp['-']=1;
 93    mp['*']=2;
 94    mp['(']=0;
 95    scanf("%d",&N);
 96    getchar();
 97    for(ca=1;ca<=N;ca++){
 98        gets(str1);
 99        gets(str2);
100        string temp1,temp2;
101        temp1=change(str1);
102        temp2=change(str2);
103        int re1=result(temp1);
104        int re2=result(temp2);
105        if(re1==re2)printf("YES\n");
106        else printf("NO\n");
107    }

108    return 0;
109}

110
111
posted on 2008-09-07 13:00 Torres 阅读(813) 评论(0)  编辑 收藏 引用 所属分类: Data Structures

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