UVa 442 Matrix Chain Multiplication

解題：利用stack
Code：

 1  #include<stdio.h>

 2  #include<stdlib.h>

 3  #include<iostream>

 4  #include<algorithm>

 5  #include<map>

 6  #include<stack>

 7  using namespace std;

 8  typedef pair<int,int> ii;

 9  bool check(ii a,ii b)

10  {

11      return a.second==b.first;

12  }

13  int mul(ii a,ii b)

14  {

15      return a.first*b.first*b.second;

16  }

17  ii ans(ii a,ii b)

18  {

19      return ii(a.first,b.second);

20  }

21  int main()

22  {

23      int n;

24      while(cin>>n)

25      {

26          map<char,ii> ma;

27          ii input[30];

28          for(int i=0; i<n; i++)

29          {

30              char ch;

31              cin>>ch;

32              cin>>input[i].first>>input[i].second;

33              ma[ch]=input[i];

34          }

35          string str;

36 

37          while(cin>>str)

38          {

39              stack<char> s;

40              bool flag=true;

41              int len=str.length();

42              int ansm=0,ind=0;

43              if(len==1)

44              {

45                  printf("0\n");

46                  continue;

47              }

48              for(int i=0; i<len; i++)

49              {

50                  if(str[i]>='A' && str[i]<='Z')

51                  {

52                      s.push(str[i]);

53                  }

54                  else if(str[i]==')')

55                  {

56                      char tmpa,tmpb;

57 

58                      tmpb=s.top();

59                      s.pop();

60                      tmpa=s.top();

61                      s.pop();

62                      ii mula=ma[tmpa],mulb=ma[tmpb];

63                      flag=check(mula,mulb);

64                      if(flag==false)

65                      {

66                          break;

67                      }

68                      else

69                      {

70                          ansm+=mul(mula,mulb);

71                          ii next=ans(mula,mulb);

72                          char tmpch=ind+'a';

73                          ma[tmpch]=next;

74                          ind++;

75                          s.push(tmpch);

76 

77                      }

78                  }

79              }

80              if(flag==false) cout<<"error"<<endl;

81              else cout<<ansm<<endl;

82          }

83      }

84      return 0;

85  }