C# 四則運算 VS Stack [PreFix（前序式）/ InFix（中序式）/ PostFix（後序式）] [Github: Postfix Expression]
C# 四則運算 VS Stack [PreFix（前序式）/ InFix（中序式）/ PostFix（後序式）] [Github: Postfix Expression]
資料來源: https://github.com/johnsonj561/PostfixArithmetics
GITHUB: https://github.com/jash-git/cs_postfix
StackNode.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace GenericStackLibrary {
/// <summary>
/// Node designed for the generic stack object
/// </summary>
/// <typeparam name="T"></typeparam>
class StackNode<T> {
/// <summary>
/// Constructor creates node with Value T and empty pointers
/// </summary>
/// <param name="value"></param>
public StackNode(T value) {
this.value = value;
prevNode = null;
}
public T value { get; set; }
public StackNode<T> prevNode { get; set; }
}
}
GenericStack.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace GenericStackLibrary {
/// <summary>
/// Stack generic stack class that stores primitive data types and user defined objects
/// </summary>
/// <typeparam name="T"></typeparam>
class GenericStack<T> {
/// <summary>
/// Constructs empty stack with no elements
/// </summary>
public GenericStack() {
top = null;
}
/// <summary>
/// Push new node onto the top of the stack
/// </summary>
/// <param name="value"></param>
public void push(T value) {
StackNode<T> newNode = new StackNode<T>(value);
size++;
//if this is the first node in stack, it is also the top
if (size == 1) {
top = newNode;
return;
}
//else bottom is already established, only change top
newNode.prevNode = top;
top = newNode;
}
/// <summary>
/// Remove and return the top element from stack.
/// Returns Null if stack is empty
/// </summary>
/// <returns></returns>
public T pop() {
//if there are elements to pop
if (size > 0) {
//get top node's value
T returnValue = top.value;
//if more node's exist, decrement top pointer to next node in stack
//garbage collector will clean up popped node once de-referenced
if(top.prevNode != null) {
top = top.prevNode;
}
size--;
return returnValue;
}
else {
return default(T);
}
}
/// <summary>
/// Returns value of stack's top most element without changing structure of stack
/// </summary>
/// <returns></returns>
public T peek() {
if(size > 0) {
return top.value;
}
Console.WriteLine("Error -> Unable to view top value of empty stack.");
return default(T);
}
/// <summary>
/// Print all elements of stack
/// </summary>
public void print() {
Console.WriteLine("\nPrinting Stack Elments" +
"\n////////////////////\n////////TOP/////////\n////////////////////");
StackNode<T> current = top;
while (current != null) {
Console.WriteLine(current.value);
current = current.prevNode;
}
Console.WriteLine("////////////////////\n//////BOTTOM////////\n////////////////////");
}
/// <summary>
/// Return false if stack size is greater than 0
/// </summary>
/// <returns></returns>
public Boolean isEmpty() {
if(size > 0) {
return false;
}
return true;
}
//define bottom and top of stack
//public StackNode<T> bottom { get; set; }
public StackNode<T> top { get; set; }
private int size;
}
}
PostfixEvaluator.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using GenericStackLibrary;
using System.Text.RegularExpressions;
namespace PostfixArithmetics {
/// <summary>
/// PostfixEvaluator provides functionality for postfix expression conversion and evaluation
/// </summary>
static class PostfixEvaluator {
/// <summary>
///
/// </summary>
/// <param name="postfix"></param>
public static string evaluatePostfixExpression(string postfix) {
char[] postfixChars = postfix.ToCharArray();
string[] tokens = postfix.Split();
//LinkedList<string> tokens = parseArithmeticExpression(postfixChars);
GenericStack<string> parsingStack = new GenericStack<string>();
//1. Scan the Postfix string from left to right.
for (int i = 0; i < tokens.Length - 1; i++) {
//2. If the scannned character is an operand, add it to the stack.
if (isOperand(tokens[i])) {
parsingStack.push(tokens[i]);
}
else {
//3. If the scanned character is an Operator, then we store the top most element of the stack(topStack) in a variable temp.
// Pop the stack. Now evaluate topStack(Operator)temp. Let the result of this operation be retVal.
// Pop the stack and Push retVal into the stack.
double operand1 = Double.Parse(parsingStack.pop());
double operand2 = Double.Parse(parsingStack.pop());
string result = "";
switch (tokens[i]) {
case "*":
result = (operand2 * operand1) + "";
break;
case "/":
result = (operand2 / operand1) + "";
break;
case "+":
result = (operand2 + operand1) + "";
break;
case "-":
result = (operand2 - operand1) + "";
break;
default:
Console.WriteLine("Error during Postfix Evaluation, unrecognized operator: " + tokens[i]);
result = "";
break;
}
parsingStack.push(result);
}
}
//5. After all characters are scanned, we will have only one element in the stack.Return topStack.
return parsingStack.pop();
}
/// <summary>
/// Static method that converts arithmetic expression from infix to postfix
/// Assumes infix input is valid arithmetic expression
/// </summary>
/// <param name="infix"></param>
/// <returns></returns>
public static string convertInfixToPostfix(string infix) {
char[] inputChars = infix.ToCharArray();
LinkedList<string> tokens = parseArithmeticExpression(inputChars);
GenericStack<string> parsingStack = new GenericStack<string>();
/* Infix -> Postfix Rules
* 1. Print operands as they arrive.
* 2. If the stack is empty or contains a left parenthesis on top, push the incoming operator onto the stack.
* 3. If the incoming symbol is a left parenthesis, push it on the stack.
* 4. If the incoming symbol is a right parenthesis, pop the stack and print the operators until you see a left parenthesis. Discard the pair of parentheses.
* 5. If the incoming symbol has higher precedence than the top of the stack, push it on the stack.
* 6. If the incoming symbol has equal precedence with the top of the stack, use association. If the association is left to right, pop and print the top of the stack and then push the incoming operator. If the association is right to left, push the incoming operator.
* 7. If the incoming symbol has lower precedence than the symbol on the top of the stack, pop the stack and print the top operator. Then test the incoming operator against the new top of stack.
* 8. At the end of the expression, pop and print all operators on the stack. (No parentheses should remain.)
*/
string postfix = "";
for (int i = 0; i < tokens.Count(); i++) {
//get incoming symbol s
string s = tokens.ElementAt(i);
//1. Print operands as they arrive.
if (Regex.IsMatch(s, @"\d*\.?\d+")) {
postfix += s + " ";
}
//3.If the incoming symbol is a left parenthesis, push it on the stack.
else if (s.Equals("(")) {
parsingStack.push(s);
}
//4. If the incoming symbol is a right parenthesis, pop the stack and print the operators until you see a left parenthesis.
// Discard the pair of parentheses.
else if (s.Equals(")")) {
while (!parsingStack.peek().Equals("(")) {
postfix += parsingStack.pop() + " ";
}
//pop the left parenthesis off stack to remove it
parsingStack.pop();
}
//else incoming symbol must be a left parenthesis or an operator
else {
//2. If the stack is empty or contains a left parenthesis on top, push the incoming operator onto the stack.
if (parsingStack.isEmpty() || parsingStack.peek().Equals("(")) {
parsingStack.push(s);
}
//5. If the incoming symbol has higher precedence than the top of the stack, push it on the stack.
else if (isHighPrecedence(s) && !isHighPrecedence(parsingStack.peek())) {
parsingStack.push(s);
}
//7. If the incoming symbol has lower precedence than the symbol on the top of the stack, pop the stack and print the top operator.
// Then test the incoming operator against the new top of stack.
else if (!isHighPrecedence(s) && isHighPrecedence(parsingStack.peek())) {
postfix += parsingStack.pop() + " ";
//now we need to check the incoming operator against new top of stack
//decementing loop index i will force loop to re-evaluate the same symbol s against new stack top
i--;
}
//6. If the incoming symbol has equal precedence with the top of the stack, use association.
// If the association is left to right, pop and print the top of the stack and then push the incoming operator.
// If the association is right to left, push the incoming operator.
// We can probably remove this condition and assume that precedence is equal...
// Stack can contain only operators and parenthesis! All numbers have already been printed to output
// If incoming is higher precedence, if incoming is lower precedence are already covered
// therefore the only option left is equal precedence
else {
postfix += parsingStack.pop() + " ";
parsingStack.push(s);
}
}
}
//8. At the end of the expression, pop and print all operators on the stack. (No parentheses should remain.)
while (!parsingStack.isEmpty()) {
postfix += parsingStack.pop() + " ";
}
return postfix;
}
/// <summary>
/// Returns true if string equals multiplication or division operator
/// </summary>
/// <param name="s"></param>
/// <returns>True if string s is multiplication or division</returns>
private static Boolean isHighPrecedence(string s) {
if (s.Equals("*") || s.Equals("/")) {
return true;
}
return false;
}
/// <summary>
/// Returns true if string value is an operand
/// </summary>
/// <param name="s"></param>
/// <returns></returns>
private static Boolean isOperand(string s) {
if(Regex.IsMatch(s, @"[\+\*\/-]{1}")) {
Console.WriteLine(s + " Is Operator");
return false;
}
Console.WriteLine(s + " Is Operand");
return true;
}
/// <summary>
/// Parses arithmetic string into array of string tokens
/// Unexpected Values (non digits, non operators) are ignored
/// </summary>
/// <param name="input"></param>
/// <returns>LinkedList<string> tokens</string></returns>
private static LinkedList<string> parseArithmeticExpression(char[] input) {
LinkedList<string> tokens = new LinkedList<string>();
string tempDigits = "";
for (int i = 0; i < input.Length; i++) {
//if char is a number or digit, store to tempDigits
//once we encounter a non digit/decimal -> flush tmepDigits into tokenList
if (Char.IsNumber(input[i]) || input[i].Equals('.')) {
tempDigits += input[i].ToString();
}
//else character is not a number or a digit, check for operators or report error
else {
switch (input[i]) {
case '+':
case '-':
case '*':
case '/':
case '(':
case ')':
//flush the tempDigits
if (tempDigits.Length > 0) {
tokens.AddLast(tempDigits);
tempDigits = "";
}
//then append new character
tokens.AddLast(input[i].ToString());
break;
//default case assumes value to be unexpected and skips over it
default:
//Console.WriteLine("Unexpected Character Being Skipped");
//Console.WriteLine("Index: " + i + ", Character = " + input[i]);
break;
}
}
}
//if last token was a number, add it to token string
if (tempDigits.Length > 0) {
tokens.AddLast(tempDigits);
}
return tokens;
}
}
}
Program.cs
/*
* Justin Johnson
* Practicing C# Data Structures
* Program uses a stack to translate a infix arithmetic expression into postfix format
*/
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using GenericStackLibrary;
using System.Text.RegularExpressions;
namespace PostfixArithmetics {
class Program {
static void Main(string[] args) {
//Get input from user
Console.WriteLine("Enter Infix Arithmetic Expression");
string userInput = Console.ReadLine();
//generate postfix output
string postfixOutput = PostfixEvaluator.convertInfixToPostfix(userInput);
Console.WriteLine("\nUser Input (Infix) = " + userInput + "\nPostfix Output = " + postfixOutput);
Console.WriteLine("\nCalculating Postfix Expression...");
string postfixResult = PostfixEvaluator.evaluatePostfixExpression(postfixOutput);
Console.WriteLine(postfixOutput + " = " + postfixResult);
Console.WriteLine("\nPress any key to terminate...");
Console.ReadKey();
}
}
}