pub fn evaluate_postfix(postfix: &[&str]) -> f64 {
let mut stack = vec![];
for &op in postfix {
match op {
"+" => {
let b = stack.pop().unwrap();
let a = stack.pop().unwrap();
stack.push(a + b);
}
"-" => {
let b = stack.pop().unwrap();
let a = stack.pop().unwrap();
stack.push(a - b);
}
"*" => {
let b = stack.pop().unwrap();
let a = stack.pop().unwrap();
stack.push(a * b);
}
"/" => {
let b = stack.pop().unwrap();
let a = stack.pop().unwrap();
stack.push(a / b);
}
operand => {
stack.push(operand.parse().unwrap());
}
}
}
stack.pop().unwrap()
}
public static double evaluatePostfix(final String[] postfix) {
final Stack<Double> stack = new Stack<>();
for (final String op : postfix) {
switch (op) {
case "+": {
final double b = stack.pop();
final double a = stack.pop();
stack.push(a + b);
break;
}
case "-": {
final double b = stack.pop();
final double a = stack.pop();
stack.push(a - b);
break;
}
case "*": {
final double b = stack.pop();
final double a = stack.pop();
stack.push(a * b);
break;
}
case "/": {
final double b = stack.pop();
final double a = stack.pop();
stack.push(a / b);
break;
}
default:
stack.push(Double.parseDouble(op));
}
}
return stack.pop();
}
function evaluatePostfix(postfix: string[]) {
const stack: number[] = [];
for (const op of postfix) {
switch (op) {
case "+": {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const b = stack.pop()!;
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const a = stack.pop()!;
stack.push(a + b);
break;
}
case "-": {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const b = stack.pop()!;
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const a = stack.pop()!;
stack.push(a - b);
break;
}
case "*": {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const b = stack.pop()!;
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const a = stack.pop()!;
stack.push(a * b);
break;
}
case "/": {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const b = stack.pop()!;
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const a = stack.pop()!;
stack.push(a / b);
break;
}
default:
stack.push(parseFloat(op));
}
}
return stack.pop();
}
type stack []float64
func (s stack) Push(v float64) stack {
return append(s, v)
}
func (s stack) Pop() (stack, float64) {
l := len(s)
return s[:l-1], s[l-1]
}
func EvaluatePostfix(postfix []string) float64 {
stack := make(stack, 0)
for _, op := range postfix {
switch op {
case "+":
{
var a, b float64
stack, b = stack.Pop()
stack, a = stack.Pop()
stack = stack.Push(a + b)
}
case "-":
{
var a, b float64
stack, b = stack.Pop()
stack, a = stack.Pop()
stack = stack.Push(a - b)
}
case "*":
{
var a, b float64
stack, b = stack.Pop()
stack, a = stack.Pop()
stack = stack.Push(a * b)
}
case "/":
{
var a, b float64
stack, b = stack.Pop()
stack, a = stack.Pop()
stack = stack.Push(a / b)
}
default:
operand, _ := strconv.ParseFloat(op, 64)
stack = stack.Push(operand)
}
}
_, operand := stack.Pop()
return operand
}
pub fn evaluate_prefix(prefix: &[&str]) -> f64 {
let mut stack = vec![];
for &op in prefix.iter().rev() {
match op {
"+" => {
let a = stack.pop().unwrap();
let b = stack.pop().unwrap();
stack.push(a + b);
}
"-" => {
let a = stack.pop().unwrap();
let b = stack.pop().unwrap();
stack.push(a - b);
}
"*" => {
let a = stack.pop().unwrap();
let b = stack.pop().unwrap();
stack.push(a * b);
}
"/" => {
let a = stack.pop().unwrap();
let b = stack.pop().unwrap();
stack.push(a / b);
}
operand => {
stack.push(operand.parse().unwrap());
}
}
}
stack.pop().unwrap()
}
public static double evaluatePrefix(final String[] prefix) {
final Stack<Double> stack = new Stack<>();
for (int i = prefix.length - 1; i >= 0; --i) {
final String op = prefix[i];
switch (op) {
case "+": {
final double a = stack.pop();
final double b = stack.pop();
stack.push(a + b);
break;
}
case "-": {
final double a = stack.pop();
final double b = stack.pop();
stack.push(a - b);
break;
}
case "*": {
final double a = stack.pop();
final double b = stack.pop();
stack.push(a * b);
break;
}
case "/": {
final double a = stack.pop();
final double b = stack.pop();
stack.push(a / b);
break;
}
default:
stack.push(Double.parseDouble(op));
}
}
return stack.pop();
}
function evaluatePrefix(prefix: string[]) {
const stack: number[] = [];
for (let i = prefix.length - 1;i >= 0;i--) {
const op = prefix[i];
switch (op) {
case "+": {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const a = stack.pop()!;
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const b = stack.pop()!;
stack.push(a + b);
break;
}
case "-": {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const a = stack.pop()!;
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const b = stack.pop()!;
stack.push(a - b);
break;
}
case "*": {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const a = stack.pop()!;
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const b = stack.pop()!;
stack.push(a * b);
break;
}
case "/": {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const a = stack.pop()!;
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const b = stack.pop()!;
stack.push(a / b);
break;
}
default:
stack.push(parseFloat(op));
}
}
return stack.pop();
}
type stack []float64
func (s stack) Push(v float64) stack {
return append(s, v)
}
func (s stack) Pop() (stack, float64) {
l := len(s)
return s[:l-1], s[l-1]
}
func EvaluatePrefix(prefix []string) float64 {
stack := make(stack, 0)
for i := len(prefix) - 1; i >= 0; i-- {
op := prefix[i]
switch op {
case "+":
{
var a, b float64
stack, a = stack.Pop()
stack, b = stack.Pop()
stack = stack.Push(a + b)
}
case "-":
{
var a, b float64
stack, a = stack.Pop()
stack, b = stack.Pop()
stack = stack.Push(a - b)
}
case "*":
{
var a, b float64
stack, a = stack.Pop()
stack, b = stack.Pop()
stack = stack.Push(a * b)
}
case "/":
{
var a, b float64
stack, a = stack.Pop()
stack, b = stack.Pop()
stack = stack.Push(a / b)
}
default:
operand, _ := strconv.ParseFloat(op, 64)
stack = stack.Push(operand)
}
}
_, operand := stack.Pop()
return operand
}
pub fn postfix_to_prefix_naive<'a>(postfix: &[&'a str]) -> Cow<'a, str> {
let mut stack = vec![];
for &op in postfix {
match op {
"+" | "-" | "*" | "/" => {
let b = stack.pop().unwrap();
let a = stack.pop().unwrap();
stack.push(Cow::from(format!("{}{}{}", op, a, b)));
}
operand => {
stack.push(Cow::from(operand));
}
}
}
stack.pop().unwrap()
}
public static String postfixToPrefixNaive(final String[] postfix) {
final Stack<String> stack = new Stack<>();
for (final String op : postfix) {
switch (op) {
case "+":
case "-":
case "*":
case "/": {
final String b = stack.pop();
final String a = stack.pop();
stack.push(op.concat(a).concat(b));
break;
}
default:
stack.push(op);
}
}
return stack.pop();
}
function postfixToPrefixNaive(postfix: string[]) {
const stack: string[] = [];
for (const op of postfix) {
switch (op) {
case "+":
case "-":
case "*":
case "/": {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const b = stack.pop()!;
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const a = stack.pop()!;
stack.push(op + a + b);
break;
}
default:
stack.push(op);
}
}
return stack.pop();
}
type stack []string
func (s stack) Push(v string) stack {
return append(s, v)
}
func (s stack) Pop() (stack, string) {
l := len(s)
return s[:l-1], s[l-1]
}
func PostfixToPrefixNaive(postfix []string) string {
stack := make(stack, 0)
for _, op := range postfix {
switch op {
case "+", "-", "*", "/":
{
var a, b string
stack, b = stack.Pop()
stack, a = stack.Pop()
stack = stack.Push(op + a + b)
}
default:
stack = stack.Push(op)
}
}
_, prefix := stack.Pop()
return prefix
}
pub fn postfix_to_prefix<'a>(postfix: &[&'a str]) -> Vec<&'a str> {
let mut stack: Vec<Vec<&str>> = vec![];
for &op in postfix {
match op {
"+" | "-" | "*" | "/" => {
let b = stack.pop().unwrap();
let a = stack.pop().unwrap();
let mut c = Vec::with_capacity(1 + a.len() + b.len());
c.push(op);
c.extend_from_slice(&a);
c.extend_from_slice(&b);
stack.push(c);
}
operand => {
stack.push(vec![operand]);
}
}
}
stack.pop().unwrap()
}
public static String[] postfixToPrefix(final String[] postfix) {
final Stack<String[]> stack = new Stack<>();
for (final String op : postfix) {
switch (op) {
case "+":
case "-":
case "*":
case "/": {
final String[] b = stack.pop();
final String[] a = stack.pop();
final String[] c = new String[1 + a.length + b.length];
c[0] = op;
System.arraycopy(a, 0, c, 1, a.length);
System.arraycopy(b, 0, c, 1 + a.length, b.length);
stack.push(c);
break;
}
default:
stack.push(new String[]{op});
}
}
return stack.pop();
}
function postfixToPrefix(postfix: string[]) {
const stack: string[][] = [];
for (const op of postfix) {
switch (op) {
case "+":
case "-":
case "*":
case "/": {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const b = stack.pop()!;
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const a = stack.pop()!;
const c = [];
c.push(op);
c.push(...a);
c.push(...b);
stack.push(c);
break;
}
default:
stack.push([op]);
}
}
return stack.pop();
}
type stack [][]string
func (s stack) Push(v []string) stack {
return append(s, v)
}
func (s stack) Pop() (stack, []string) {
l := len(s)
return s[:l-1], s[l-1]
}
func PostfixToPrefix(postfix []string) []string {
stack := make(stack, 0)
for _, op := range postfix {
switch op {
case "+", "-", "*", "/":
{
var a, b []string
stack, b = stack.Pop()
stack, a = stack.Pop()
c := make([]string, 1+len(a)+len(b))
c[0] = op
copy(c[1:], a)
copy(c[(1+len(a)):], b)
stack = stack.Push(c)
}
default:
stack = stack.Push([]string{op})
}
}
_, prefix := stack.Pop()
return prefix
}
pub fn prefix_to_postfix_naive(prefix: &[&str]) -> String {
let mut stack = vec![];
for &op in prefix.iter().rev() {
match op {
"+" | "-" | "*" | "/" => {
let a = stack.pop().unwrap();
let b = stack.pop().unwrap();
stack.push(format!("{}{}{}", a, b, op));
}
operand => {
stack.push(operand.to_string());
}
}
}
stack.pop().unwrap()
}
pub fn prefix_to_postfix<'a>(prefix: &[&'a str]) -> Vec<&'a str> {
let mut stack: Vec<Vec<&str>> = vec![];
for &op in prefix.iter().rev() {
match op {
"+" | "-" | "*" | "/" => {
let a = stack.pop().unwrap();
let b = stack.pop().unwrap();
let mut c = Vec::with_capacity(1 + a.len() + b.len());
c.extend_from_slice(&a);
c.extend_from_slice(&b);
c.push(op);
stack.push(c);
}
operand => {
stack.push(vec![operand]);
}
}
}
stack.pop().unwrap()
}
再優化一下prefix_to_postfix函數。
pub fn prefix_to_postfix<'a>(prefix: &[&'a str]) -> Vec<&'a str> {
let mut stack: Vec<Vec<&str>> = vec![];
for &op in prefix.iter().rev() {
match op {
"+" | "-" | "*" | "/" => {
let mut a = stack.pop().unwrap();
let b = stack.pop().unwrap();
a.reserve(b.len() + 1);
a.extend_from_slice(&b);
a.push(op);
stack.push(a);
}
operand => {
stack.push(vec![operand]);
}
}
}
stack.pop().unwrap()
}
public static String prefixToPostfixNaive(final String[] prefix) {
final Stack<String> stack = new Stack<>();
for (int i = prefix.length - 1; i >= 0; --i) {
final String op = prefix[i];
switch (op) {
case "+":
case "-":
case "*":
case "/": {
final String a = stack.pop();
final String b = stack.pop();
stack.push(a.concat(b).concat(op));
break;
}
default:
stack.push(op);
}
}
return stack.pop();
}
public static String[] prefixToPostfix(final String[] prefix) {
final Stack<String[]> stack = new Stack<>();
for (int i = prefix.length - 1; i >= 0; --i) {
final String op = prefix[i];
switch (op) {
case "+":
case "-":
case "*":
case "/": {
final String[] a = stack.pop();
final String[] b = stack.pop();
final String[] c = new String[1 + a.length + b.length];
System.arraycopy(a, 0, c, 0, a.length);
System.arraycopy(b, 0, c, a.length, b.length);
c[c.length - 1] = op;
stack.push(c);
break;
}
default:
stack.push(new String[]{op});
}
}
return stack.pop();
}
function prefixToPostfixNaive(prefix: string[]) {
const stack: string[] = [];
for (let i = prefix.length - 1;i >= 0;i--) {
const op = prefix[i];
switch (op) {
case "+":
case "-":
case "*":
case "/": {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const a = stack.pop()!;
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const b = stack.pop()!;
stack.push(a + b + op);
break;
}
default:
stack.push(op);
}
}
return stack.pop();
}
function prefixToPostfix(prefix: string[]) {
const stack: string[][] = [];
for (let i = prefix.length - 1;i >= 0;i--) {
const op = prefix[i];
switch (op) {
case "+":
case "-":
case "*":
case "/": {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const a = stack.pop()!;
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const b = stack.pop()!;
const c = [];
c.push(...a);
c.push(...b);
c.push(op);
stack.push(c);
break;
}
default:
stack.push([op]);
}
}
return stack.pop();
}
type stringArrayStack [][]string
func (s stringArrayStack) Push(v []string) stringArrayStack {
return append(s, v)
}
func (s stringArrayStack) Pop() (stringArrayStack, []string) {
l := len(s)
return s[:l-1], s[l-1]
}
type stringStack []string
func (s stringStack) Push(v string) stringStack {
return append(s, v)
}
func (s stringStack) Pop() (stringStack, string) {
l := len(s)
return s[:l-1], s[l-1]
}
func PrefixToPostfixNaive(prefix []string) string {
stack := make(stringStack, 0)
for i := len(prefix) - 1; i >= 0; i-- {
op := prefix[i]
switch op {
case "+", "-", "*", "/":
{
var a, b string
stack, a = stack.Pop()
stack, b = stack.Pop()
stack = stack.Push(a + b + op)
}
default:
stack = stack.Push(op)
}
}
_, postfix := stack.Pop()
return postfix
}
func PrefixToPostfix(prefix []string) []string {
stack := make(stringArrayStack, 0)
for i := len(prefix) - 1; i >= 0; i-- {
op := prefix[i]
switch op {
case "+", "-", "*", "/":
{
var a, b []string
stack, a = stack.Pop()
stack, b = stack.Pop()
c := make([]string, 1+len(a)+len(b))
copy(c, a)
copy(c[len(a):], b)
c[len(c)-1] = op
stack = stack.Push(c)
}
default:
stack = stack.Push([]string{op})
}
}
_, postfix := stack.Pop()
return postfix
}
pub fn postfix_to_infix_naive(postfix: &[&str]) -> String {
let mut stack = vec![];
for &op in postfix {
match op {
"+" | "-" | "*" | "/" => {
let b = stack.pop().unwrap();
let a = stack.pop().unwrap();
stack.push(format!("({}{}{})", a, op, b));
}
operand => {
stack.push(operand.to_string());
}
}
}
stack.pop().unwrap()
}
pub fn postfix_to_infix<'a>(postfix: &[&'a str]) -> Vec<&'a str> {
let mut stack: Vec<Vec<&str>> = vec![];
for &op in postfix {
match op {
"+" | "-" | "*" | "/" => {
let b = stack.pop().unwrap();
let a = stack.pop().unwrap();
let mut c = Vec::with_capacity(3 + a.len() + b.len());
c.push("(");
c.extend_from_slice(&a);
c.push(op);
c.extend_from_slice(&b);
c.push(")");
stack.push(c);
}
operand => {
stack.push(vec![operand]);
}
}
}
stack.pop().unwrap()
}
pub fn prefix_to_infix_naive(prefix: &[&str]) -> String {
let mut stack = vec![];
for &op in prefix.iter().rev() {
match op {
"+" | "-" | "*" | "/" => {
let a = stack.pop().unwrap();
let b = stack.pop().unwrap();
stack.push(format!("({}{}{})", a, op, b));
}
operand => {
stack.push(operand.to_string());
}
}
}
stack.pop().unwrap()
}
pub fn prefix_to_infix<'a>(prefix: &[&'a str]) -> Vec<&'a str> {
let mut stack: Vec<Vec<&str>> = vec![];
for &op in prefix.iter().rev() {
match op {
"+" | "-" | "*" | "/" => {
let a = stack.pop().unwrap();
let b = stack.pop().unwrap();
let mut c = Vec::with_capacity(3 + a.len() + b.len());
c.push("(");
c.extend_from_slice(&a);
c.push(op);
c.extend_from_slice(&b);
c.push(")");
stack.push(c);
}
operand => {
stack.push(vec![operand]);
}
}
}
stack.pop().unwrap()
}
public static String postfixToInfixNaive(final String[] postfix) {
final Stack<String> stack = new Stack<>();
for (final String op : postfix) {
switch (op) {
case "+":
case "-":
case "*":
case "/": {
final String b = stack.pop();
final String a = stack.pop();
stack.push("(".concat(a).concat(op).concat(b).concat(")"));
break;
}
default:
stack.push(op);
}
}
return stack.pop();
}
public static String[] postfixToInfix(final String[] postfix) {
final Stack<String[]> stack = new Stack<>();
for (final String op : postfix) {
switch (op) {
case "+":
case "-":
case "*":
case "/": {
final String[] b = stack.pop();
final String[] a = stack.pop();
final String[] c = new String[3 + a.length + b.length];
c[0] = "(";
System.arraycopy(a, 0, c, 1, a.length);
c[1 + a.length] = op;
System.arraycopy(b, 0, c, 2 + a.length, b.length);
c[c.length - 1] = ")";
stack.push(c);
break;
}
default:
stack.push(new String[]{op});
}
}
return stack.pop();
}
public static String prefixToInfixNaive(final String[] prefix) {
final Stack<String> stack = new Stack<>();
for (int i = prefix.length - 1; i >= 0; --i) {
final String op = prefix[i];
switch (op) {
case "+":
case "-":
case "*":
case "/": {
final String a = stack.pop();
final String b = stack.pop();
stack.push("(".concat(a).concat(op).concat(b).concat(")"));
break;
}
default:
stack.push(op);
}
}
return stack.pop();
}
public static String[] prefixToInfix(final String[] prefix) {
final Stack<String[]> stack = new Stack<>();
for (final String op : prefix) {
switch (op) {
case "+":
case "-":
case "*":
case "/": {
final String[] a = stack.pop();
final String[] b = stack.pop();
final String[] c = new String[3 + a.length + b.length];
c[0] = "(";
System.arraycopy(a, 0, c, 1, a.length);
c[1 + a.length] = op;
System.arraycopy(b, 0, c, 2 + a.length, b.length);
c[c.length - 1] = ")";
stack.push(c);
break;
}
default:
stack.push(new String[]{op});
}
}
return stack.pop();
}
function postfixToInfixNaive(postfix: string[]) {
const stack: string[] = [];
for (const op of postfix) {
switch (op) {
case "+":
case "-":
case "*":
case "/": {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const b = stack.pop()!;
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const a = stack.pop()!;
stack.push("(" + a + op + b + ")");
break;
}
default:
stack.push(op);
}
}
return stack.pop();
}
function postfixToInfix(postfix: string[]) {
const stack: string[][] = [];
for (const op of postfix) {
switch (op) {
case "+":
case "-":
case "*":
case "/": {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const b = stack.pop()!;
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const a = stack.pop()!;
const c = [];
c.push("(");
c.push(...a);
c.push(op);
c.push(...b);
c.push(")");
stack.push(c);
break;
}
default:
stack.push([op]);
}
}
return stack.pop();
}
function prefixToInfixNaive(prefix: string[]) {
const stack: string[] = [];
for (let i = prefix.length - 1;i >= 0;i--) {
const op = prefix[i];
switch (op) {
case "+":
case "-":
case "*":
case "/": {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const a = stack.pop()!;
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const b = stack.pop()!;
stack.push("(" + a + op + b + ")");
break;
}
default:
stack.push(op);
}
}
return stack.pop();
}
function prefixToInfix(prefix: string[]) {
const stack: string[][] = [];
for (let i = prefix.length - 1;i >= 0;i--) {
const op = prefix[i];
switch (op) {
case "+":
case "-":
case "*":
case "/": {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const a = stack.pop()!;
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const b = stack.pop()!;
const c = [];
c.push("(");
c.push(...a);
c.push(op);
c.push(...b);
c.push(")");
stack.push(c);
break;
}
default:
stack.push([op]);
}
}
return stack.pop();
}
type stringArrayStack [][]string
func (s stringArrayStack) Push(v []string) stringArrayStack {
return append(s, v)
}
func (s stringArrayStack) Pop() (stringArrayStack, []string) {
l := len(s)
return s[:l-1], s[l-1]
}
type stringStack []string
func (s stringStack) Push(v string) stringStack {
return append(s, v)
}
func (s stringStack) Pop() (stringStack, string) {
l := len(s)
return s[:l-1], s[l-1]
}
func PostfixToInfixNaive(postfix []string) string {
stack := make(stringStack, 0)
for _, op := range postfix {
switch op {
case "+", "-", "*", "/":
{
var a, b string
stack, b = stack.Pop()
stack, a = stack.Pop()
stack = stack.Push("(" + a + op + b + ")")
}
default:
stack = stack.Push(op)
}
}
_, infix := stack.Pop()
return infix
}
func PostfixToInfix(postfix []string) []string {
stack := make(stringArrayStack, 0)
for _, op := range postfix {
switch op {
case "+", "-", "*", "/":
{
var a, b []string
stack, b = stack.Pop()
stack, a = stack.Pop()
c := make([]string, 3+len(a)+len(b))
c[0] = "("
copy(c[1:], a)
c[1+len(a)] = op
copy(c[(2+len(a)):], b)
c[len(c)-1] = ")"
stack = stack.Push(c)
}
default:
stack = stack.Push([]string{op})
}
}
_, infix := stack.Pop()
return infix
}
func PrefixToInfixNaive(prefix []string) string {
stack := make(stringStack, 0)
for i := len(prefix) - 1; i >= 0; i-- {
op := prefix[i]
switch op {
case "+", "-", "*", "/":
{
var a, b string
stack, a = stack.Pop()
stack, b = stack.Pop()
stack = stack.Push("(" + a + op + b + ")")
}
default:
stack = stack.Push(op)
}
}
_, infix := stack.Pop()
return infix
}
func PrefixToInfix(prefix []string) []string {
stack := make(stringArrayStack, 0)
for i := len(prefix) - 1; i >= 0; i-- {
op := prefix[i]
switch op {
case "+", "-", "*", "/":
{
var a, b []string
stack, a = stack.Pop()
stack, b = stack.Pop()
c := make([]string, 3+len(a)+len(b))
c[0] = "("
copy(c[1:], a)
c[1+len(a)] = op
copy(c[(2+len(a)):], b)
c[len(c)-1] = ")"
stack = stack.Push(c)
}
default:
stack = stack.Push([]string{op})
}
}
_, infix := stack.Pop()
return infix
}
fn get_priority(op: &str) -> Option<u8> {
match op {
"+" | "-" => Some(1),
"*" | "/" => Some(2),
_ => None,
}
}
pub fn infix_to_postfix<'a>(infix: &[&'a str]) -> Vec<&'a str> {
let mut out = vec![];
let mut stack: Vec<&str> = vec![];
for &op in infix {
if let Some(priority) = get_priority(op) {
if let Some(temp) = stack.last().copied() {
if priority <= get_priority(temp).unwrap() {
while let Some(temp) = stack.pop() {
out.push(temp);
}
}
}
stack.push(op);
} else {
out.push(op);
}
}
while let Some(temp) = stack.pop() {
out.push(temp);
}
out
}
public static int getPriority(final String op) {
switch (op) {
case "+":
case "-":
return 1;
case "*":
case "/":
return 2;
default:
return 0;
}
}
public static String[] infixToPostfix(final String[] infix) {
final ArrayList<String> out = new ArrayList<>();
final Stack<String> stack = new Stack<>();
for (final String op : infix) {
final int priority = getPriority(op);
if (priority > 0) {
if (!stack.isEmpty()) {
final String temp = stack.peek();
if (priority <= getPriority(temp)) {
while (!stack.isEmpty()) {
out.add(stack.pop());
}
}
}
stack.push(op);
} else {
out.add(op);
}
}
while (!stack.isEmpty()) {
out.add(stack.pop());
}
return out.toArray(new String[out.size()]);
}
function getPriority(op: string) {
switch (op) {
case "+":
case "-":
return 1;
case "*":
case "/":
return 2;
default:
return 0;
}
}
function infixToPostfix(infix: string[]) {
const out: string[] = [];
const stack: string[] = [];
for (const op of infix) {
const priority = getPriority(op);
if (priority > 0) {
if (stack.length > 0) {
const temp = stack[stack.length - 1];
if (priority <= getPriority(temp)) {
while (stack.length > 0) {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
out.push(stack.pop()!);
}
}
}
stack.push(op);
} else {
out.push(op);
}
}
while (stack.length > 0) {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
out.push(stack.pop()!);
}
return out;
}
type stack []string
func (s stack) Push(v string) stack {
return append(s, v)
}
func (s stack) Pop() (stack, string) {
l := len(s)
return s[:l-1], s[l-1]
}
func getPriority(op string) int {
switch op {
case "+", "-":
return 1
case "*", "/":
return 2
default:
return 0
}
}
func InfixToPostfix(infix []string) []string {
out := make([]string, 0)
stack := make(stack, 0)
for _, op := range infix {
priority := getPriority(op)
if priority > 0 {
if len(stack) > 0 {
temp := stack[len(stack)-1]
if priority <= getPriority(temp) {
for len(stack) > 0 {
var e string
stack, e = stack.Pop()
out = append(out, e)
}
}
}
stack = stack.Push(op)
} else {
out = append(out, op)
}
}
for len(stack) > 0 {
var e string
stack, e = stack.Pop()
out = append(out, e)
}
return out
}
pub fn infix_to_postfix<'a>(infix: &[&'a str]) -> Vec<&'a str> {
let mut out = vec![];
let mut stack: Vec<&str> = vec![];
for &op in infix {
if let Some(priority) = get_priority(op) {
while let Some(temp) = stack.last().copied() {
if priority > get_priority(temp).unwrap() {
break;
}
out.push(temp);
unsafe {
stack.set_len(stack.len() - 1);
}
}
stack.push(op);
} else {
out.push(op);
}
}
while let Some(temp) = stack.pop() {
out.push(temp);
}
out
}
public static String[] infixToPostfix(final String[] infix) {
final ArrayList<String> out = new ArrayList<>();
final Stack<String> stack = new Stack<>();
for (final String op : infix) {
final int priority = getPriority(op);
if (priority > 0) {
while (!stack.isEmpty()) {
final String temp = stack.peek();
if (priority > getPriority(temp)) {
break;
}
out.add(stack.pop());
}
stack.push(op);
} else {
out.add(op);
}
}
while (!stack.isEmpty()) {
out.add(stack.pop());
}
return out.toArray(new String[out.size()]);
}
function infixToPostfix(infix: string[]) {
const out: string[] = [];
const stack: string[] = [];
for (const op of infix) {
const priority = getPriority(op);
if (priority > 0) {
while (stack.length > 0) {
const temp = stack[stack.length - 1];
if (priority > getPriority(temp)) {
break;
}
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
out.push(stack.pop()!);
}
stack.push(op);
} else {
out.push(op);
}
}
while (stack.length > 0) {
out.push(stack.pop());
}
return out;
}
func InfixToPostfix(infix []string) []string {
out := make([]string, 0)
stack := make(stack, 0)
for _, op := range infix {
priority := getPriority(op)
if priority > 0 {
for len(stack) > 0 {
temp := stack[len(stack)-1]
if priority > getPriority(temp) {
break
}
var e string
stack, e = stack.Pop()
out = append(out, e)
}
stack = stack.Push(op)
} else {
out = append(out, op)
}
}
for len(stack) > 0 {
var e string
stack, e = stack.Pop()
out = append(out, e)
}
return out
}
#{{{
\begin{eqnarray}
a + b - c &\rightarrow& a \text{ } b \text{ } + \text{ } c \text{ } - \nonumber \\
a + ( b - c ) &\rightarrow& a \text{ } b \text{ } c \text{ } - \text{ } +
\end{eqnarray}
}}}#
pub fn infix_to_postfix<'a>(infix: &[&'a str]) -> Vec<&'a str> {
let mut out = vec![];
let mut stack: Vec<&str> = vec![];
for &op in infix {
match op {
"(" => {
stack.push("(");
}
")" => {
while let Some(temp) = stack.pop() {
if temp == "(" {
break;
}
out.push(temp);
}
}
_ => {
if let Some(priority) = get_priority(op) {
while let Some(temp) = stack.last().copied() {
if temp == "(" || priority > get_priority(temp).unwrap() {
break;
}
out.push(temp);
unsafe {
stack.set_len(stack.len() - 1);
}
}
stack.push(op);
} else {
out.push(op);
}
}
}
}
while let Some(temp) = stack.pop() {
out.push(temp);
}
out
}
public static String[] infixToPostfix(final String[] infix) {
final ArrayList<String> out = new ArrayList<>();
final Stack<String> stack = new Stack<>();
for (final String op : infix) {
switch (op) {
case "(":
stack.push("(");
break;
case ")":
while (!stack.isEmpty()) {
final String temp = stack.pop();
if (temp.equals("(")) {
break;
}
out.add(temp);
}
break;
default: {
final int priority = getPriority(op);
if (priority > 0) {
while (!stack.isEmpty()) {
final String temp = stack.peek();
if (temp.equals("(") || priority > getPriority(temp)) {
break;
}
out.add(stack.pop());
}
stack.push(op);
} else {
out.add(op);
}
}
}
}
while (!stack.isEmpty()) {
out.add(stack.pop());
}
return out.toArray(new String[out.size()]);
}
function infixToPostfix(infix: string[]) {
const out: string[] = [];
const stack: string[] = [];
for (const op of infix) {
switch (op) {
case "(":
stack.push("(");
break;
case ")":
while (stack.length > 0) {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const temp = stack.pop()!;
if (temp === "(") {
break;
}
out.push(temp);
}
break;
default: {
const priority = getPriority(op);
if (priority > 0) {
while (stack.length > 0) {
const temp = stack[stack.length - 1];
if (temp === "(" || priority > getPriority(temp)) {
break;
}
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
out.push(stack.pop()!);
}
stack.push(op);
} else {
out.push(op);
}
}
}
}
while (stack.length > 0) {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
out.push(stack.pop()!);
}
return out;
}
func InfixToPostfix(infix []string) []string {
out := make([]string, 0)
stack := make(stack, 0)
for _, op := range infix {
switch op {
case "(":
stack = stack.Push("(")
case ")":
for len(stack) > 0 {
var temp string
stack, temp = stack.Pop()
if temp == "(" {
break
}
out = append(out, temp)
}
default:
{
priority := getPriority(op)
if priority > 0 {
for len(stack) > 0 {
temp := stack[len(stack)-1]
if temp == "(" || priority > getPriority(temp) {
break
}
var e string
stack, e = stack.Pop()
out = append(out, e)
}
stack = stack.Push(op)
} else {
out = append(out, op)
}
}
}
}
for len(stack) > 0 {
var e string
stack, e = stack.Pop()
out = append(out, e)
}
return out
}
pub fn infix_to_prefix<'a>(infix: &[&'a str]) -> Vec<&'a str> {
let mut out = vec![];
let mut stack: Vec<&str> = vec![];
for &op in infix.iter().rev() {
match op {
")" => {
stack.push(")");
}
"(" => {
while let Some(temp) = stack.pop() {
if temp == ")" {
break;
}
out.push(temp);
}
}
_ => {
if let Some(priority) = get_priority(op) {
while let Some(temp) = stack.pop() {
if temp == ")" || priority > get_priority(temp).unwrap() {
break;
}
out.push(temp);
unsafe {
stack.set_len(stack.len() - 1);
}
}
stack.push(op);
} else {
out.push(op);
}
}
}
}
while let Some(temp) = stack.pop() {
out.push(temp);
}
out.reverse();
out
}
public static String[] infixToPrefix(final String[] infix) {
final ArrayList<String> out = new ArrayList<>();
final Stack<String> stack = new Stack<>();
for (int i = infix.length - 1; i >= 0; --i) {
final String op = infix[i];
switch (op) {
case ")":
stack.push(")");
break;
case "(":
while (!stack.isEmpty()) {
final String temp = stack.pop();
if (temp.equals(")")) {
break;
}
out.add(temp);
}
break;
default: {
final int priority = getPriority(op);
if (priority > 0) {
while (!stack.isEmpty()) {
final String temp = stack.peek();
if (temp.equals(")") || priority > getPriority(temp)) {
break;
}
out.add(stack.pop());
}
stack.push(op);
} else {
out.add(op);
}
}
}
}
while (!stack.isEmpty()) {
out.add(stack.pop());
}
Collections.reverse(out);
return out.toArray(new String[out.size()]);
}
function infixToPrefix(infix: string[]) {
const out: string[] = [];
const stack: string[] = [];
for (let i = infix.length - 1;i >= 0;i--) {
const op = infix[i];
switch (op) {
case ")":
stack.push(")");
break;
case "(":
while (stack.length > 0) {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
const temp = stack.pop()!;
if (temp === ")") {
break;
}
out.push(temp);
}
break;
default: {
const priority = getPriority(op);
if (priority > 0) {
while (stack.length > 0) {
const temp = stack[stack.length - 1];
if (temp === ")" || priority > getPriority(temp)) {
break;
}
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
out.push(stack.pop()!);
}
stack.push(op);
} else {
out.push(op);
}
}
}
}
while (stack.length > 0) {
// eslint-disable-next-line @typescript-eslint/no-non-null-assertion
out.push(stack.pop()!);
}
out.reverse();
return out;
}
type stack []string
func (s stack) Push(v string) stack {
return append(s, v)
}
func (s stack) Pop() (stack, string) {
l := len(s)
return s[:l-1], s[l-1]
}
func InfixToPrefix(infix []string) []string {
out := make([]string, 0)
stack := make(stack, 0)
for i := len(infix) - 1; i >= 0; i-- {
op := infix[i]
switch op {
case ")":
stack = stack.Push(")")
case "(":
for len(stack) > 0 {
var temp string
stack, temp = stack.Pop()
if temp == ")" {
break
}
out = append(out, temp)
}
default:
{
priority := getPriority(op)
if priority > 0 {
for len(stack) > 0 {
temp := stack[len(stack)-1]
if temp == ")" || priority > getPriority(temp) {
break
}
var e string
stack, e = stack.Pop()
out = append(out, e)
}
stack = stack.Push(op)
} else {
out = append(out, op)
}
}
}
}
for len(stack) > 0 {
var e string
stack, e = stack.Pop()
out = append(out, e)
}
for i, j := 0, len(out)-1; i < j; i, j = i+1, j-1 {
out[i], out[j] = out[j], out[i]
}
return out
}
這樣的實作方式會讓中序式的基本計算順序變成由右向左。例如a - b - c就會變成(a - (b - c))，等同於a - b + c，會跟原算式不相等。所以如果寫出以上的程式那就錯了。(許多網站提供的程式碼或是網頁計算機就是這種有問題的)
