【日常学习】【栈】【表达式求值】Uva442 - Matrix Chain Multiplication题解

￡神魔★判官ぃ 2022-08-07 02:00 14阅读 0赞

之前一直没有写过栈的典型程序，这里写一个。这个程序完全是我独立写出来的，我还没有看ruka上的标程，或许会有些不同。

题目来源：University of Ulm Local Contest 1996  Uva 442 POJ 2246

简而言之，就是按一定的规则求（A（BC））这样的表达式的值，是典型的表达式求值题目

这次写了伪代码，虽然也不是伪代码，就是一点思路

//伪代码
     int main(){
     	初始化；读入 ； 
    	  //如（A（BC））
    	  遇到左括号就进栈，先把A的2个数据进栈 10 20
    	  又是左括号，BC都进栈 
    	  这时候遇到右括号，两个栈顶元素出栈 需要四个变量存储a1 a2 b1 b2；a2和b1必须相等，否则输出error 
    	  计算a1*a2*b2 ans+ 此时BC合并为10 5（20已被去除）即  a1 b2入栈 
    	  遇到右括号 同理 直到结束 
     }

这是基本思路 括号实际充当了入站出站的标志

野生代码：

#include<iostream>
    #include<stack>
    #include<cstdio>
    #include<string>//POJ要加string 
    using namespace std;
    
    struct matrix{//notice!!!
    	int a,b;
    	matrix(int a=0,int b=0):a(a),b(b){}	//结构体变量a,b赋初值
    }m[26];//以结构体为基类型的数组
    
    stack<int> s;
    
    int main(){
    	int n;
    	cin>>n;//忘了写这一句 后果是int类型读入了A 于是遇到问题关闭 !!!TUT 
    	char ch;
    	for (int i=0;i<n;i++){
    		cin>>ch;
    		cin>>m[ch-'A'].a>>m[ch-'A'].b;
    	}
    	string str;
    	while (cin>>str){
    		if (isalpha(str[0])){
    			cout<<0<<endl;
    			continue;
    		}
    		bool er=false; 
    		int a1,a2,b1,b2,ans=0;//按顺序先入栈 
    		for (int i=1;i<=str.size()-1;i++){//第二遍刚开始少了等号 答案错误 
    			if (str[i]=='(') continue;
    			else if ((str[i]==')')&&(!s.empty())){
    				b2=s.top();s.pop();
    				b1=s.top();s.pop();
    				a2=s.top();s.pop();
    				a1=s.top();s.pop();
    				if (a2!=b1){
    					cout<<"error"<<endl;
    					er=true;
    					break;
    				}
    				ans+=a1*a2*b2;
    				s.push(a1);
    				s.push(b2);
    			}
    			else{
    				int x=str[i]-'A';
    				s.push(m[x].a);
    				s.push(m[x].b);
    			}
    		}
    		(!er)?cout<<ans<<endl:er=false;//防止输出error的情况下还输出ans（=0）
    	}
    	return 0;
    }

前两天发现的神奇现象，i/o/iostream头文件里包括string，今天又有了新的发现：还是加上string吧，因为不加string的代码在ZOJAC，在POJCE了TUT

基本上，栈的典型应用，结构体的基础，在这里都有了。

——乘彼垝垣，以望复关。不见复关，泣涕涟涟；既见复关，载笑载言。