逆波兰式

  1 using System;
  2 using System.Collections.Generic;
  3 using System.Linq;
  4 using System.Text;
  5 using System.Threading.Tasks;
  6 
  7 namespace EvaluateReversePolishNotation
  8 {
  9     class Program
 10     {
 11         /// <summary>
 12         /// 逆波兰式：  
 13         /// ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
 14         /// ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6
 15         /// 这一题就是写程序计算逆波兰式的结果，遍历表达式，碰到操作数入栈，碰到操作符就从栈顶取出两个操作数，
 16         /// 再将计算后的结果入栈，最后栈中剩余的唯一操作数就是计算结果。  
 17         /// </summary>
 18         /// <param name="args"></param>
 19 
 20         public class Node
 21         {
 22             public int val;
 23             public Node next;
 24             public Node(int x)
 25             {
 26                 val = x;
 27             }
 28         }
 29 
 30         public class Stack
 31         {
 32             public Node top;
 33             public void valIn(Node n)
 34             {
 35                 if (n != null)
 36                 {
 37                     Node temp = top;
 38                     top = n;
 39                     top.next = temp;
 40                 }
 41                 else
 42                 {
 43                     top = n;
 44                     top.next = null;
 45                 }
 46             }
 47 
 48             public Node valOut()
 49             {
 50                 if (top == null)
 51                 {
 52                     return null;
 53                 }
 54                 else
 55                 {
 56                     Node temp = new Node(top.val);
 57                     top = top.next;
 58                     return temp;
 59                 }
 60             }
 61         }
 62         public static int calculte(string a, Node x, Node y, ref int result)
 63         {
 64             switch (a)
 65             {
 66                 case "+":
 67                     result = x.val + y.val;
 68                     return result;
 69                 case "-":
 70                     result = x.val - y.val;
 71                     return result;
 72                 case "*":
 73                     result = x.val * y.val;
 74                     return result;
 75                 case "/":
 76                     result = x.val / y.val;
 77                     return result;
 78                 default:
 79                     return 0;
 80             }
 81         }
 82         static void Main(string[] args)
 83         {
 84             string[] list = { "4", "13", "5", "/", "+" };
 85             Stack sk = new Stack();
 86             Node inn = null;
 87             Node outn_first = null;
 88             Node outn_second = null;
 89             int num = 0;
 90 
 91             foreach (var a in list)
 92             {
 93                 if (int.TryParse(a, out num))
 94                 {
 95                     inn = new Node(num);
 96                     sk.valIn(inn);
 97                     sk.top = inn;
 98                 }
 99                 else
100                 {
101                     if (sk.top != null)
102                     {
103                         int result = 0;
104                         outn_first = sk.valOut();
105                         outn_second = sk.valOut();
106                         result = calculte(a, outn_second, outn_first, ref result);
107                         sk.valIn(new Node(result));
108                     }
109                 }
110             }
111             Console.WriteLine(sk.top.val);
112             Console.ReadKey();
113         }
114     }
115 }