STL----栈的初步应用

STL----栈的初步应用（学习笔记）

栈的模型如下

栈就像一个装满衣服的桶，要想往里面放衣服，只能放在最上面；而要想取出衣服，则必须先从上面去取。简称为上进上出。

应用实例

1. HDU 5479 ---- Scaena Felix

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

Problem Description
Given a parentheses sequence consist of ‘(’ and ‘)’, a modify can filp a parentheses, changing ‘(’ to ‘)’ or ‘)’ to ‘(’.

If we want every not empty substring of this parentheses sequence not to be “paren-matching”, how many times at least to modify this parentheses sequence?

For example, “()”,"(())","()()" are “paren-matching” strings, but “((”, “)(”, “((()” are not.

Input
The first line of the input is a integer T, meaning that there are T test cases.

Every test cases contains a parentheses sequence S only consists of ‘(’ and ‘)’.

1≤|S|≤1,000.

Output
For every test case output the least number of modification.

Sample Input

3
()
((((
(())

Sample Output

1
0
2

思路：
题目要求，输出一串括号中，至少变动多少次单个括号，才能使该括号串变为“非配对型括号串”（ not to be “paren-matching” ）。
问题也可转化为：在括号串中，存在多少对相邻且配对的括号 （eg. )(()(( 加粗的括号配对），就最少变动多少次单个括号。

这时就能利用栈的思想了：每配对一对括号，就把这一对括号的左半边从栈中删除，并令计数器+1，最后输出计数器的值，即为至少变动的次数。

代码如下：

#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main()
{
    int t; cin>>t;
    cin.get(); // cin.sync()过不了，我也不知道为啥...哪位好心的大佬看到这条注释，欢迎在评论区解答
    while(t--)
    {
        stack<char>s;
        string line;
        int sum=0;
        getline( cin , line , '\n' );
        for ( int i=0 ; i<(int)line.length() ; i++ )
        {
            if ( s.empty() )
            {   // 若栈为空，把当前字符放入栈中
                s.push( line[i] ); // 入栈操作
                continue;
            }
            else
            {
                char tmp=s.top();  // 提取栈顶字符  top函数返回栈顶变量的引用
                if ( tmp == '(' && line[i] == ')' )
                {   // 匹配成功，删除栈顶的"("
                    s.pop(); // 删除操作
                    sum++;
                }
                else
                {   // 匹配失败，当前字符入栈
                    s.push( line[i] );
                }
            }
        }
        cout<<sum<<endl;
    }
    return 0;
}

2. HDU 1237 ---- 简单计算器

Problem Description
读入一个只包含 +, -, *, / 的非负整数计算表达式，计算该表达式的值。

Input
测试输入包含若干测试用例，每个测试用例占一行，每行不超过200个字符，整数和运算符之间用一个空格分隔。没有非法表达式。当一行中只有0时输入结束，相应的结果不要输出。

Output
对每个测试用例输出1行，即该表达式的值，精确到小数点后2位。

Sample Input

1 + 2
4 + 2 * 5 - 7 / 11
0

Sample Output

3.00
13.36

这道题目我最初的想法是用两个栈，乘除法运算完的数据放在一个栈里面，另一个栈由于最后的加减法运算（将之前的栈中的所有数据存进来，这时数据顺序正好颠倒，可进行运算），但是缺点是需要把之前的符号储存在一个数组里，比较麻烦，而且我也不会用哈哈

其实一个栈就可以完美解决：只需要把减号的右操作数取相反数，最后把整个栈里的数累加就好了！
另外，在处理四则运算时，可以利用switch语句，建立四则运算的不同处理语句

代码如下：

#include <iostream>
#include <iomanip>
#include <stack>
#include <string> // getline函数需要string和iostream头文件
using namespace std;

int main()
{
    string s1;
    getline( cin , s1 , '\n' );
    stack<double>num;
    while ( s1 != "0" )
    {
        /* 利用栈的思想
            加减法优先级较低，可以将加减法的左操作数压入栈底，最后做加减运算
            乘除法优先级高，一旦遇到乘除号，立即让左操作数出栈，与右操作数运算后再进栈
            乘除法做完最后做加减：
            此处两种做法：1：再设一个栈，将之前的栈中的所有数据存进来，这时数据顺序正好颠倒，
                                          可进行运算。（但是需要把之前的加减号存到一个数组里面）
                                     2：减号的右操作数直接取相反数，最后全加起来即可
        */
        char status='+'; // 第一个数若不为负数，则处理方式默认为加号的右操作数
        double tmp=0;
        for ( int i=0 ; i < (int)s1.length() ; i++ )
        {
            if ( s1[i]== ' ' ) continue;
            else if ( s1[i] == '+' ) status='+';
                else if ( s1[i] == '-' ) status='-';
                    else if ( s1[i] == '*' ) status='*';
                        else if ( s1[i] == '/' ) status='/';
                            else
                            {
                                tmp=0;  // tmp临时变量储存数字
                                while ( s1[i] >= '0' && s1[i] <= '9' )
                                {   // 此处相当于进位处理：上一个数向前移动一位，需要乘以10，再加上当前数字。
                                    tmp=tmp*10+( s1[i] - '0' );
                                    i++;
                                }
                                i--; // 遇到空格，回退一位
                                switch ( status )
                                {   // 根据此数字之前的符号，分别进行不同操作
                                    case '+': num.push( tmp ); break; // 存入栈顶
                                    case '-': num.push( -tmp ); break; // 去相反数，存入栈顶
                                    case '*':
                                        {
                                            double top = num.top() * tmp;  // 取栈顶的数，与当前数（'*'的右操作数）相乘
                                            num.pop( ); // 删除栈顶的数
                                            num.push ( top ); break;     // 在栈顶存入新数
                                        }
                                    case '/':
                                        {
                                            double top = num.top() / tmp;  // 取栈顶的数，与当前数（'/'的右操作数）相除
                                            num.pop( ); // 删除栈顶的数
                                            num.push ( top ); break;     // 在栈顶存入新数
                                        }
                                }
                            }
        }
        double aswr=0;
        while( !num.empty() )
        {   // 把所有数加起来
            aswr+=num.top();
            num.pop();
        }
        cout<<setprecision(2)<<fixed<< aswr <<endl;
        getline( cin , s1 , '\n' );
    }
    return 0;
}

未完待续…