栈的应用

一、平衡符号

1、知识点补充：

开放符号指左括号，封闭符号指右括号。

2、特点：

程序中开放符号和封闭符号成对出现；

就近原则，封闭符号与离他最近的开放符号相对应；

3、算法

伪代码：

 1 Algorithm{
 2     Make an empty stack;
 3     while(read in a character ch)
 4     {
 5         if( ch is a open symbol)    
 6             push(c,S);
 7         else if(ch is a close symbol)
 8             {
 9                 if(isEmpty){error;exit;}
10                 else
11                 {
12                     if(Top(S) is not match ){error,exit;}
13                     else pop(S);
14                 }
15             }    
16     }//end whileLoop
17     
18     if(！isEmpty){error;exit;}
19  }

实现：

 1 int checkSymbol(Stack *S)
 2 {
 3     char ch;
 4     printf("input characters as {,} or (,)or [,] 
");
 5     printf("and # to quit
");
 6     while((ch=scanf_s("%c",&ch))!='#')           //输入平衡字符
 7     {
 8         if(ch=='{'||ch=='['||ch=='(')            /*开放符号*/
 9             S = a->Push(ch,S);
10         else if(ch=='}'||ch==']'||ch==')')       /*封闭符号*/
11             { 
12                 if(isEmpty(S))                   /*栈里无字符*/
13                    cout << "stack is empty." << endl;
14                 else 
15                 {
16                     switch(ch)
17                     {
18                         case '}':
19                             if( Top(S) != '{' )   //不匹配
20                             cout << "not match" << endl;
21                             else 
22                             break;                //匹配成功
23                         
24                         case ')':
25                             if( Top(S) != '(' )
26                             cout << "not match" << endl;
27                             else 
28                             break; 
29                         
30                         case ']':
31                             if( Top(S) != '[' )
32                             cout << "not match" << endl;
33                             else break; 
34                     }
35          /*匹配成功，将栈中匹配成功的符号弹出*/
36                    S = a->pop(S);
37                 }
38             }
39     
40     }
41     if( !isEmpty(S) )  //如果最后栈里还有字符，则说明未匹配完，即出错
42         cout << "the stack is not empty last" << endl;
43     else 
44         return 0;     //成功
45 }

二、后缀表达式（不需要括号）

后缀表达式：6 5 2 3 + 8 * + 3 + *

6 5 5 8 * + 3 + *

6 5 40 + 3 + *

6 45 3 + *

6 48 *

288

 1 int Algorithm{
 2 
 3      Make an empty stack S;
 4      while(read in a character nu)
 5      {
 6          if( nu is a number)    
 7              push(nu,S);
 8          else if(nu is a mathematical symbol)
 9              {
10                  int a = pop(S);  //pop means pop and top
11 　　　　　　　　　　int b = pop(S);
12 　　　　　　　　　　push(a nu b,S);
13              }    
14      }　　　　　　　　　　　　　　　　//end whileLoop　　
15      return pop(S);
16 }

中缀表达式（有括号，正常式子）向后缀表达式的转换：

中缀表达式： a + b * c + ( d * e + f ) * g -> 后缀表达式：a b c * + d e * f + g * +

操作数，操作符原则：

1、操作数直接输出

2、操作符 ‘*’ 优先级高于 ‘+’ ，‘(’ 优先级最高

3、操作符读入后与栈顶元素比较：若该操作符优先级高于栈顶则该操作符入栈；否则该操作符在栈里元素输出后入栈。

4、‘(’优先级最高入栈，仅在遇到 ‘)’ 时,将栈中符号依次输出；'('弹出（注意不是输出）