利用栈实现中缀表达式的简单计算
表达式计算
实现简单的中缀表达式计算：
- 实现对于输入的中缀表达式字符串进行计算
- 对于输入表达式错误能够识别并输出表达式错误
- 括号不匹配
- 计算结束后，运算符栈里还有元素
- 遇到除数字和运算符和括号的字符之外的其他字符
解决步骤：
-
实现
MyStack类，使用泛型，即在创建该类时传入数据类型，确定成员变量顺序数组的数据类型，写栈的基本方法：判满、判空、入栈、弹栈、返回栈顶元素 -
构造两个栈：一个存储运算符的栈operator（char）（包括+ - * / ），再构造一个存储操作数的栈operand（double）
-
对于operator，栈里面只存储运算符，对于入栈有运算符优先级比较，具体有4个规则
- ‘*’ ‘/’ 大于 ’+‘ ’-‘
- 运算遵循左结合性，即先出现的运算符优先级更高
- 对于左括号’（‘，优先级最高
- 当右括号入栈时，operator一直出栈，直到遇到左括号
即遵循如果operator栈顶元素运算符的优先级大于等于当前运算符的优先级，栈顶元素要出栈，进行运算，之后将当前运算符入栈，栈中肯定保持当前运算符的优先级大于下面所有运算符
-
对于operand，栈里面只存储数字，会有从这个栈里取出栈顶两个元素进行计算，将计算结果压栈
-
-
主方法中，按以下步骤：
-
input接受用户输入字符串（要求使用英文）
-
调用expression方法，传入输入字符数组
在expression方法中，先用判断括号是否匹配方法，若不匹配，提示错误信息，结束程序。否则依次遍历得到每个字符，并记录遍历到的：
如果是空格跳过
- 如果字符是数字，使用while继续遍历，直到当前字符不是数字，将遍历得到的字符拼接之后转为double类型压入栈中
- 如果是运算符，将栈顶元素于当前元素的优先级进行比较，如果栈顶元素优先级大于等于当前运算符，则栈顶元素出栈，进行运算，当前字符进栈
- 如果是左括号，压栈
- 如果是右括号，只要没有到左括号，那么operator一直出栈，进行运算
- 如果都不是，表明遇到其他不合法字符，提示表达式输入错误，结束程序
遍历完表达式之后，operator栈里还有一个元素，operand栈里还有两个元素，将最后计算结果压栈，最后返回最终结果。
-
用到的辅助方法：
-
判断是否是运算符bool isop(char c);
-
求运算符优先级int precede(char c);
-
计算两数运算结果double twoResult(char op,double a,double b);
-
检查括号是否匹配bool IsParenthesesMatch(char[] str);
实现步骤：
- 创建存放字符的栈stack
- 遇到左括号，入栈
- 遇到右括号，如果栈为空或者栈顶元素不是是左括号，返回false；如果是左括号，出栈
- 到最后如果栈非空返回false
考虑以下不匹配情况：
- 括号数不匹配
- 顺序不匹配
-
-
上面考虑到的表达式错误很少，仅包含括号不匹配，表达式中有除加减乘除、左右括号和空格意外的其他字符，对于运算符相邻没有考虑到，比如"3+2**6-9+(12-3)*2".
运算也只限于输入是整数，进行加减乘除运算。
主要可以学习到的是熟练使用栈，以及了解栈在解题中的作用。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace 表达式计算
{
internal class MyStack<T>
{
private T[] values;
private int top;
public MyStack()
{
values = new T[10];
top = 0;
}
public bool IsEmpty()
{
return top == 0;
}
public bool IsFull()
{
return top == values.Length;
}
public void Push(T value)
{
if (IsFull())
{
T[] newArray = new T[values.Length * 2];
Array.Copy(values, newArray, values.Length);
values = newArray;
}
values[top++] = value;
}
public T Pop()
{
if(IsEmpty())
{
throw new InvalidOperationException("Stack is empty.");
}
return values[--top];
}
public T Peek()
{
if (IsEmpty())
{
throw new InvalidOperationException("Stack is empty.");
}
return values[top - 1];
}
public int Count()
{
return top;
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Linq.Expressions;
using System.Text;
using System.Threading.Tasks;
namespace 表达式计算
{
internal class Program
{
static void Main(string[] args)
{
Console.WriteLine("请输入表达式：");
//"3+(5-(8/2)*7)*2+100"
//"3+8-7"
//"3+2**6-9+(12-3)*2"
//"3**2"
string input = "(5 + 3) * (7 - 2) + 18 / (4 + 2) - 9";
double result = expression(input.ToCharArray());
Console.WriteLine(result);
}
public static double expression(char[] str)
{
if (!IsParenthesesMatch(str))
{
Console.WriteLine("表达式括号不匹配");
Environment.Exit(1);
}
//创建运算符栈
MyStack<char> Operator = new MyStack<char>();
//创建操作数栈
MyStack<double> Operand = new MyStack<double>();
for(int i = 0; i < str.Length; i++)
{
if (str[i] ==' ')
{
continue;
}
else if (isDigit(str[i]))
{
string s = str[i].ToString();
i++;
while ((i <= str.Length - 1) && isDigit(str[i]))
{
s+= str[i].ToString();
i++;
}
//执行到这里，str[i]不是数字字符，i要回退1，因为下次i会自增
i--;
Operand.Push(double.Parse(s));
}
else if (isop(str[i]))
{
//如果当前栈为空
if (Operator.IsEmpty())
{
Operator.Push(str[i]);
continue;
}
; //如果栈顶元素优先级大于等于当前运算符的优先级
if (precede(Operator.Peek()) >= precede(str[i]))
{
//运算符栈顶元素出栈，操作数出栈
if (Operand.Count() >= 2)
{
Operand.Push(twoResult(Operator.Pop(), Operand.Pop(), Operand.Pop()));
}
else
{
//表明可能有两个优先级相等的运算符相邻
Console.WriteLine("表达式有错误。");
Environment.Exit(1);
}
}
//由于不管栈顶元素优先级是否大于等于当前运算符的优先级，当前运算符都要入栈
Operator.Push(str[i]);
}
else if (str[i] == '(')
{
Operator.Push(str[i]);
}
else if (str[i] == ')')
{
char opstr;
while((opstr = Operator.Pop()) != '(')
{
Operand.Push(twoResult(opstr, Operand.Pop(), Operand.Pop()));
}
}
//其他字符
else
{
Console.WriteLine("表达式有错误。");
Environment.Exit(1);
}
}
//对剩余在栈里的元素进行操作
while (!Operator.IsEmpty())
{
Operand.Push(twoResult(Operator.Pop(), Operand.Pop(), Operand.Pop()));
}
//返回最终结果
return Operand.Peek();
}
public static bool isDigit(char c)
{
if(c >= '0' && c <= '9')
{
return true;
}
else
{
return false;
}
}
public static bool isop(char c)
{
if (c == '+' || c == '-' || c == '*' || c == '/')
{
return true;
}
return false;
}
public static int precede(char c)
{
switch (c)
{
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
default:
return 0;
}
}
public static double twoResult(char op,double a,double b)
{
switch (op)
{
case '+':
return b + a;
case '-':
return b - a;
case '*':
return b * a;
case '/':
if(a == 0)
{
throw new DivideByZeroException("除数不能为零");
}
return b / a;
default:
throw new ArgumentException("无效的运算符");
}
}
public static bool IsParenthesesMatch(char[] str)
{
//保存括号
MyStack<char> temp= new MyStack<char>();
foreach (char c in str)
{
//c为括号
if(c == '(')
{
temp.Push(c);
}
else if(c == ')')
{
if(temp.IsEmpty()||temp.Peek() != '(')
{
return false;
}
//将左括号出栈
temp.Pop();
}
}
return temp.IsEmpty();
}
}
}