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

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

之前一直没有写过栈的典型程序，这里写一个。这个程序完全是我独立写出来的，我还没有看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;
}