c#逆波兰算法解决有括号的表达式
时间: 2024-02-13 21:05:09 浏览: 30
逆波兰算法同样适用于有括号的表达式。我们可以使用一个栈来处理括号。当我们遇到左括号时,将其压入栈中。当我们遇到右括号时,我们可以从栈中弹出所有操作符,直到遇到左括号为止。最后,我们将所有弹出的操作符应用于操作数。最后,我们将计算结果压入栈中。
以下是一个处理有括号的逆波兰算法实现的示例代码:
```csharp
using System;
using System.Collections.Generic;
public class Program
{
public static void Main()
{
string expression = "2 * (3 + 4)";
Console.WriteLine("Expression: " + expression);
Console.WriteLine("Result: " + Evaluate(expression));
}
public static double Evaluate(string expression)
{
Stack<double> stack = new Stack<double>();
Stack<char> operators = new Stack<char>();
foreach (char c in expression)
{
if (char.IsDigit(c))
{
stack.Push(double.Parse(c.ToString()));
}
else if (c == '(')
{
operators.Push(c);
}
else if (c == ')')
{
while (operators.Peek() != '(')
{
ApplyOperator(stack, operators.Pop());
}
operators.Pop(); // remove the left parenthesis
}
else if (IsOperator(c))
{
while (operators.Count > 0 && Precedence(c) <= Precedence(operators.Peek()))
{
ApplyOperator(stack, operators.Pop());
}
operators.Push(c);
}
}
while (operators.Count > 0)
{
ApplyOperator(stack, operators.Pop());
}
return stack.Pop();
}
private static bool IsOperator(char c)
{
return c == '+' || c == '-' || c == '*' || c == '/';
}
private static int Precedence(char c)
{
switch (c)
{
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
default:
throw new ArgumentException("Invalid operator: " + c);
}
}
private static void ApplyOperator(Stack<double> stack, char op)
{
double operand2 = stack.Pop();
double operand1 = stack.Pop();
switch (op)
{
case '+':
stack.Push(operand1 + operand2);
break;
case '-':
stack.Push(operand1 - operand2);
break;
case '*':
stack.Push(operand1 * operand2);
break;
case '/':
stack.Push(operand1 / operand2);
break;
default:
throw new ArgumentException("Invalid operator: " + op);
}
}
}
```
在上面的代码中,我们使用了两个栈,一个用于存储操作数,另一个用于存储操作符。我们遍历表达式中的每个字符,如果它是一个数字,则将其压入操作数栈中。如果它是一个运算符,则将其压入操作符栈中。如果它是左括号,则将其压入操作符栈中。如果它是右括号,则从操作符栈中弹出所有操作符,直到遇到左括号为止,并将这些操作符应用于操作数。最后,我们返回操作数栈中的唯一元素,这就是表达式的计算结果。
在上面的示例中,我们可以计算 "2 * (3 + 4)" 这个表达式,它的计算结果是 14。