栈

1. POJ 1363 rails 栈的模拟

其实就是给一个出栈的序列，看这个序列是否合法。在push进栈的同时，与输入的序列进行比较，如果栈顶元素等于当前序列的元素，就继续出栈，一直到元素不相等，或者栈空为止。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
using namespace std;

int main(){
     int n,i,k;
     int arr[1000];
     while(cin>>n && n){
          stack<int> s;
          while(cin>>arr[0] && arr[0]){
               for(int i = 1; i < n; i++)
                   cin>>arr[i];
               for(i = 1,k=0; i<=n; i++){
                    s.push(i);
                    while(s.top() == arr[k]){
                         if(!s.empty()) s.pop();
                         k++;
                         if(s.empty()) break;
                    }
               }
               if(k==n)
                    cout<<"Yes"<<endl;
               else
                    cout<<"No"<<endl;
          }
          cout<<endl;
     }
     
     return 0;
}

2. 表达式求值
设立两个栈，一个用来放操作数，一个用来放操作符，从前往后遍历表达式，如果遇到操作数，则入栈，遇到操作符，就用当前遍历到的操作符和目前操作符栈顶的符号做优先级比较，如果当前操作符的优先级小于栈顶的操作符，那么就从栈顶弹出一个操作符，从操作数的栈中弹出2个操作数，进行计算。

需要注意的是，由于栈的先进后出，第二个弹出的元素要作为第一个操作数，计算完成后，把计算结果压入栈。

要保证运算符栈顶元素的优先级是最大的。

代码实现过程中，一般在运算符栈中先push一个优先级最小的运算符，然后在表达式后面加一个优先级次小的运算符

#include<iostream>
#include<stack>
#include<string>
using namespace std;
 
int Priority(char ch){
    if(ch == '#')
        return 0;
    else if(ch == '$')
        return 1;
    else if(ch == '+' || ch == '-')
        return 2;
    else
        return 3;
}
 
double Cal(double a, double b, char ch){
    if(ch == '+')
        return a+b;
    else if(ch == '-')
        return a-b;
    else if(ch == '*')
        return a*b;
    else
        return a/b;
}
 
int GetNum(string s, int& index){
    int res = 0;
    while(isdigit(s[index])){
        res = res * 10 + s[index] - '0';
        index++;
    }
    return res;
}
 
int main(){
    string str;
    stack<double> data;
    stack<char> oper;
    cin>>str;
    str += '$';
    oper.push('#');
    int i = 0;
    while(i < str.length()){
        if(isdigit(str[i])){
            int num = GetNum(str, i);  // 得到数字
            data.push(num);
        }
        else{
            char o = str[i];  // 当前的运算符
            if(Priority(o) > Priority(oper.top())){
                oper.push(o);
                i++;
            }
            else{
                char ch = oper.top();
                oper.pop();
                double num1 = data.top();
                data.pop();
                double num2 = data.top();
                data.pop();
                data.push(Cal(num2, num1, ch));
                //cout<<data.top()<<endl;
            }
        }
    }
    cout<<data.top()<<endl;
    return 0;
}