弄了很久中缀表达式转前缀和后缀表达式的概念,后缀表达式也称为逆波兰式表达式，前缀表达式称为波兰式表达式。用C#仿照简单实现了他们之间的转换以及求值。不要喷我，因为概念都是一样的，不要以为是抄袭，哈哈。
程序中有很多不足的地方（比如不支持大于10的整数，因为我直接使用String.ToCharArray()肯定不妥），希望大家一起改进，谢谢。以下贴出全部代码：using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;namespace ReversePolishNotation
{
class Program
{
static void Main(string[] args)
{
//中缀表达式转化为后缀表达式
Trans trans = new Trans();
Eval eval = new Eval();
string s = Console.ReadLine().Replace(" ",string.Empty);
Console.WriteLine("Input string: "+s);
string translated = trans.TranslateRPN(s);
Console.WriteLine("RPN string: "+translated);
double res = eval.EvaluateRPN(translated);
Console.WriteLine("Valud: "+res.ToString("f2")); //中缀表达式转化为前缀表达式
translated = trans.TranslatePN(s);
Console.WriteLine("PN string: " + translated);
res = eval.EvaluatePN(translated);
Console.WriteLine("Valud: " + res.ToString("f2"));
}
} //Eval: Evaluate RPN string
//single digits, treated as doubles, and operators
class Eval
{
Stack<double> stack = null; public Eval()
{
stack = new Stack<double>();
} public double EvaluateRPN(String s)
{
double op1 = 0.0, op2 = 0.0, res = 0.0;
char[] array = s.ToCharArray();
for (int i = 0; i < array.Length; i++)
{
char ch = array[i];
if (Char.IsDigit(ch))
{
stack.Push((double)(ch - '0')); //Push digit as double
}
else //Char is a operator
{
if (stack.Count == 0)
Error(1);
else
op2 = stack.Pop(); if (stack.Count == 0)
Error(2);
else
op1 = stack.Pop(); res = Evaluate(ch, op1, op2);
stack.Push(res);
}
} if (stack.Count == 0)
Error(4);
else
res = stack.Pop(); if (stack.Count != 0)
Error(5); return res;
} public double EvaluatePN(String s)
{
double op1 = 0.0, op2 = 0.0, res = 0.0;
char[] array = s.ToCharArray();
for (int i = array.Length-1; i >=0; i--)
{
char ch = array[i];
if (Char.IsDigit(ch))
{
stack.Push((double)(ch - '0')); //Push digit as double
}
else //Char is a operator
{
if (stack.Count == 0)
Error(1);
else
op2 = stack.Pop(); if (stack.Count == 0)
Error(2);
else
op1 = stack.Pop(); res = Evaluate(ch, op1, op2);
stack.Push(res);
}
} if (stack.Count == 0)
Error(4);
else
res = stack.Pop(); if (stack.Count != 0)
Error(5); return res;
} private double Evaluate(char ch, double op1, double op2)
{
switch (ch)
{
case '+': return op1 + op2;
case '-': return op1 - op2;
case '*': return op1 * op2;
case '/': return op1 / op2;
case '^': return Math.Pow(op1, op2);
default: Error(3); return 0;
}
} private void Error(int num)
{
Console.WriteLine("Error number: " + num);
Environment.Exit(num);
}
}
程序中有很多不足的地方（比如不支持大于10的整数，因为我直接使用String.ToCharArray()肯定不妥），希望大家一起改进，谢谢。以下贴出全部代码：using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;namespace ReversePolishNotation
{
class Program
{
static void Main(string[] args)
{
//中缀表达式转化为后缀表达式
Trans trans = new Trans();
Eval eval = new Eval();
string s = Console.ReadLine().Replace(" ",string.Empty);
Console.WriteLine("Input string: "+s);
string translated = trans.TranslateRPN(s);
Console.WriteLine("RPN string: "+translated);
double res = eval.EvaluateRPN(translated);
Console.WriteLine("Valud: "+res.ToString("f2")); //中缀表达式转化为前缀表达式
translated = trans.TranslatePN(s);
Console.WriteLine("PN string: " + translated);
res = eval.EvaluatePN(translated);
Console.WriteLine("Valud: " + res.ToString("f2"));
}
} //Eval: Evaluate RPN string
//single digits, treated as doubles, and operators
class Eval
{
Stack<double> stack = null; public Eval()
{
stack = new Stack<double>();
} public double EvaluateRPN(String s)
{
double op1 = 0.0, op2 = 0.0, res = 0.0;
char[] array = s.ToCharArray();
for (int i = 0; i < array.Length; i++)
{
char ch = array[i];
if (Char.IsDigit(ch))
{
stack.Push((double)(ch - '0')); //Push digit as double
}
else //Char is a operator
{
if (stack.Count == 0)
Error(1);
else
op2 = stack.Pop(); if (stack.Count == 0)
Error(2);
else
op1 = stack.Pop(); res = Evaluate(ch, op1, op2);
stack.Push(res);
}
} if (stack.Count == 0)
Error(4);
else
res = stack.Pop(); if (stack.Count != 0)
Error(5); return res;
} public double EvaluatePN(String s)
{
double op1 = 0.0, op2 = 0.0, res = 0.0;
char[] array = s.ToCharArray();
for (int i = array.Length-1; i >=0; i--)
{
char ch = array[i];
if (Char.IsDigit(ch))
{
stack.Push((double)(ch - '0')); //Push digit as double
}
else //Char is a operator
{
if (stack.Count == 0)
Error(1);
else
op2 = stack.Pop(); if (stack.Count == 0)
Error(2);
else
op1 = stack.Pop(); res = Evaluate(ch, op1, op2);
stack.Push(res);
}
} if (stack.Count == 0)
Error(4);
else
res = stack.Pop(); if (stack.Count != 0)
Error(5); return res;
} private double Evaluate(char ch, double op1, double op2)
{
switch (ch)
{
case '+': return op1 + op2;
case '-': return op1 - op2;
case '*': return op1 * op2;
case '/': return op1 / op2;
case '^': return Math.Pow(op1, op2);
default: Error(3); return 0;
}
} private void Error(int num)
{
Console.WriteLine("Error number: " + num);
Environment.Exit(num);
}
}
class Trans
{
Stack<char> stack = null;
Stack<char> stackInAndOut = null; public Trans()
{
stack = new Stack<char>();
stackInAndOut = new Stack<char>();
} //Trans: translate input arith expr to RPN string
//Rules for each input char (go on to next input char unless otherwise stated)
//Fetch next char, call it ch
//1. If ch is an operand, move it to output
//From now on ch is an operator or '(' or ')'.
//2. If stack is empty, add ch to stack
//3. If ch is '(', add ch to stack
//From now on, stack is not empt. Use top for its top char
//4. If ch is ')', remove chars from stack and output down to '(' on stack, whick is thrown away.
//5. If top is '(', add ch to stack.
//From now on, both ch and top are regular operators
//6. If prec(ch)>prec(top), add ch to stack.
//7. If prec(ch)<prec(top), move top to output, and DO NOT MOVE ON TO NEXT INPUT CHAR.
//8. if prec(ch)==prec(top) and left-to-right associativity, move top to output, and DO NOT MOVE ON TO NEXT INPUT CHAR.
//9. if prec(ch)==prec(top) and right-to-left associativity, add top to stack.
//10. At end, move everything on stack to output.
public string TranslateRPN(string s)
{
double op1 = 0.0, op2 = 0.0, op3 = 0.0;
string output = ""; //Output string
char ch, top;
int i = 0; //Index in input string
char[] arrary = s.ToCharArray(); while (i < arrary.Length)
{
bool moveOn = true;
ch = arrary[i]; //Before rule 1
if (Char.IsDigit(ch)) //Rule 1: digit to output
output += ch;
else if (stack.Count == 0 || ch == '(') //Rule 2 and 3
stack.Push(ch);
else //Stack isn't empty
{
top = stack.Peek(); //Before rule 4
if (ch == ')') //Rule 4
while (true)
{
if ((top = stack.Pop()) == '(')
break; //normal termination
output += top;
if (stack.Count == 0)
Error(1);
}
else if (top == '(') //Rule 5
stack.Push(ch);
else if (Prec(ch) > Prec(top) || (Prec(ch) == Prec(top) && Assoc(ch) == 'r')) //Rule 6 and 9
stack.Push(ch);
else if (Prec(ch) < Prec(top) || (Prec(ch) == Prec(top) && Assoc(ch) == 'l')) //Rule 7 and 8
{
output += top; //move top to output
stack.Pop();
moveOn = false;
}
} if (moveOn)
i++;
} while (stack.Count != 0) //Rule 10
output += stack.Pop(); return output;
} //Trans: Translate the input arith expr to prev string
//Reverse the input string
//Rules for each input char (go on to next input char unless otherwise stated)
//Fetch next char, call it ch
//1. If ch is an operand, move it to output
//From now on ch is an operator or '(' or ')'.
//2. If stack is empty, add ch to stack
//3. If ch is ')', add ch to stack
//From now on, stack is not empt. Use top for its top char
//4. If ch is '(', remove chars from stack and output down to ')' on stack, whick is thrown away.
//5. If top is ')', add ch to stack.
//From now on, both ch and top are regular operators
//6. If prec(ch)>prec(top), add ch to stack.
//7. If prec(ch)<prec(top), move top to output, and DO NOT MOVE ON TO NEXT INPUT CHAR.
//8. if prec(ch)==prec(top) and left-to-right associativity, move top to output, and DO NOT MOVE ON TO NEXT INPUT CHAR.
//9. if prec(ch)==prec(top) and right-to-left associativity, add top to stack.
//10. At end, move everything on stack to output.
//11. Reverse the output string
public string TranslatePN(string s)
{
double op1 = 0.0, op2 = 0.0, op3 = 0.0;
string output = ""; //Output string
char ch, top;
//int i = 0; //Index in input string
char[] arrary = s.ToCharArray(); for (int j = 0; j < arrary.Length; j++)
{
stackInAndOut.Push(arrary[j]);
} while (stackInAndOut.Count!=0)
{
bool moveOn = true;
ch = stackInAndOut.Peek();
if (Char.IsDigit(ch)) //Rule 1
output += ch;
else if (stack.Count == 0 || ch == ')') //Rule 2 and 3
stack.Push(ch);
else //Stack is not empty
{
top = stack.Peek();
if (ch == '(') //Before rule 4
while (true)
{
if ((top = stack.Pop()) == ')')
break;
output += top;
if (stack.Count == 0)
Error(1);
}
else if (top == ')') //Rule 5
stack.Push(ch);
else if (Prec(ch) > Prec(top) || (Prec(ch) == Prec(top) && Assoc(ch) == 'r')) //Rule 6 and 9
stack.Push(ch);
else if (Prec(ch) < Prec(top) || (Prec(ch) == Prec(top) && Assoc(ch) == 'l')) //Rule 7 and 8
{
output += top; //move top to output
stack.Pop();
moveOn = false;
}
} if (moveOn)
stackInAndOut.Pop();
} while (stack.Count != 0) //Rule 10
output += stack.Pop(); if (stackInAndOut.Count != 0)
Error(1);
char[] chars = output.ToCharArray();
for (int j = 0; j < chars.Length; j++)
{
stackInAndOut.Push(chars[j]);
} output = "";
while (stackInAndOut.Count != 0)
output += stackInAndOut.Pop(); return output;
} private void Error(int num)
{
Console.WriteLine("Error number: " + num);
Environment.Exit(num);
} //prec: return int precedence of operators
private int Prec(char ch)
{
switch (ch)
{
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
default:
return -1;
}
} //assoc: return 'l' for left-to-right, and 'r' for right-to-left
private char Assoc(char ch)
{
switch (ch)
{
case '+':
case '-':
case '*':
case '/':
return 'l';
case '^':
return 'r';
default:
return '?';
}
}
}
}