C#数据结构与算法系列（九）：栈实现综合计算器（中缀表达式）
2024-10-09 04:43:51
1.问题介绍
2.实现思路
3.代码实现
第一个版本（采用这个）
public class ArrayStack
{
private int _maxSize;
private int[] _arr;
private int _top = -; /// <summary>
/// 初始化栈
/// </summary>
/// <param name="maxSize"></param>
public ArrayStack(int maxSize)
{
_maxSize = maxSize;
_arr = new int[_maxSize];
} /// <summary>
/// 栈是否为空
/// </summary>
/// <returns></returns>
public bool IsEmpty() => _top == -; /// <summary>
/// 栈是否满
/// </summary>
/// <returns></returns>
public bool IsFull() => _top == _maxSize-; /// <summary>
/// 入栈
/// </summary>
/// <param name="value"></param>
public void Push(int value)
{
if (IsFull())
{
Console.WriteLine("栈满");
}
else
{
_top++;
_arr[_top] = value;
}
}
/// <summary>
/// 出栈
/// </summary>
/// <returns></returns>
public int Pop()
{
if (IsEmpty())
{
throw new Exception("栈空");
}
int value = _arr[_top]; _top--; return value;
} /// <summary>
/// 栈列表
/// </summary>
public void List()
{
if (IsEmpty())
{
Console.WriteLine("栈空");
}
else
{
for (int i = _top; i >= ; i--)
{
Console.WriteLine($"stack:[{i}]={_arr[i]}");
}
}
} /// <summary>
/// 返回当前栈顶的值
/// </summary>
/// <returns></returns>
public int Peek() => _arr[_top]; /// <summary>
/// 优先级判断
/// </summary>
/// <param name="oper"></param>
/// <returns></returns>
public int Priority(int oper)
{
if (oper == '*' || oper == '/')
{
return ;
}
else if (oper == '+' || oper == '-')
{
return ;
}
else return -;
}
/// <summary>
/// 计算
/// </summary>
/// <param name="num1"></param>
/// <param name="num2"></param>
/// <param name="oper"></param>
/// <returns></returns>
public int Cal(int num1, int num2, int oper)
{
int result = ;
switch (oper)
{
case '+':
result = num1 + num2;
break;
case '-':
result = num2 - num1; //注意顺序
break;
case '*':
result = num1 * num2;
break;
case '/':
result = num2 / num1; //注意顺序
break;
default:
break;
}
return result;
} /// <summary>
/// 判断是否是操作符
/// </summary>
/// <param name="val"></param>
/// <returns></returns>
public bool IsOper(char val)
{
return val == '-' || val == '+' || val == '*' || val == '/';
}
}
using System; namespace DataStructure
{
public class Calculator
{
public static void Test()
{
string expression = "300+2*3+2-1"; ArrayStack numStack = new ArrayStack(); ArrayStack operStack = new ArrayStack(); //把字符串转换成char数组
char[] arr = expression.ToCharArray(); /*
public unsafe char[] ToCharArray() int length = this.Length;
char[] array = new char[length];
if (length > 0)
{
fixed (char* ptr = &this.m_firstChar)
{
fixed (char* ptr2 = array)
{
string.wstrcpy(ptr2, ptr, length);
}
}
}
return array; */
//结果
int result = ; int num1 = ; int num2 = ; int oper = ; string keepNum = ""; for (int i = ; i < arr.Length; i++)
{
//判断是不是操作符
if (operStack.IsOper(arr[i]))
{
//如果不是空的
if (!operStack.IsEmpty())
{
//如果符号栈中有操作符，就进行比较，如果当前操作符的优先级小于或等于栈中的操作符，就需要从栈中pop出两个数
//再从符号栈中pop出一个符号，进行运算，将得到结果，入数栈，然后再把当前操作符入符号栈
if (operStack.Priority(arr[i]) <= operStack.Priority(operStack.Peek()))
{
num1 = numStack.Pop(); num2 = numStack.Pop(); oper = operStack.Pop(); //计算
result = numStack.Cal(num1, num2, oper); numStack.Push(result); operStack.Push(arr[i]);
}
else
{
//如果当前操作符的优先级大于栈中的操作符就直接入符号栈
operStack.Push(arr[i]);
}
}
else
{
//为空就直接入符号栈
operStack.Push(arr[i]);
}
}
else
{
//把字符转成字符串
keepNum += arr[i]; for (int j = i + ; j < arr.Length; j++)
{
//判断arr[i]的面是否是操作符 如果不是则拼接
if (!numStack.IsOper(arr[j]))
{
keepNum += arr[j]; i++;//当确定后一个是数字的时候 索引也要跟着往后移
}
//如果是则终止
else break;
} numStack.Push(int.Parse(keepNum)); //一定要置空，否则会保留上一次操作
keepNum = "";
}
}
//当数字占和符号栈都不为空的情况下才进循环
while (!operStack.IsEmpty() && !numStack.IsEmpty())
{
//当符号栈为空的时候就跳出循环
if (operStack.IsEmpty()) break; num1 = numStack.Pop(); num2 = numStack.Pop(); oper = operStack.Pop(); result = numStack.Cal(num1, num2, oper); numStack.Push(result);
} Console.WriteLine($"表达式{expression}={numStack.Pop()}");
}
}
}
第二个版本
public class ArrayStack {
private int maxSize;
private int[] stack;
private int top = -1;
public ArrayStack(int maxSize) {
this.maxSize = maxSize;
stack = new int[maxSize];
}
public boolean isEmpty() {
return top == -1;
}
public boolean isFull() {
return top == maxSize;
}
public void push(int value) {
if (isFull()) {
System.out.println("栈已满！");
} else {
top++;
stack[top] = value;
}
}
public int pop() {
if (isEmpty()) {
throw new RuntimeException("栈为空");
}
int result = stack[top];
top--;
return result;
}
public void list() {
if (isEmpty()) {
System.out.println("栈为空");
} else {
for (int i = top; i >= 0; i--) {
System.out.printf("stack[%d]=%d\n", i, stack[i]);
}
}
}
public int peek() {
return stack[top];
}
public boolean isOperate(int vaule) {
return vaule == '*' || vaule == '/' || vaule == '+' || vaule == '-';
}
public int calculate(int num1, int num2, int operate) {
switch (operate) {
case '*':
return num1 * num2;
case '/':
return num2 / num1;
case '+':
return num1 + num2;
case '-':
return num2 - num1;
default:
return 0;
}
}
public int priority(int operate) {
if (operate == '*' || operate == '/') {
return 1;
} else if (operate == '+' || operate == '-') {
return 0;
} else return -1;
}
}
public class Calculator {
public static void main(String[] args) {
String expression = "3+2*5-1";
ArrayStack numStack = new ArrayStack(10);
ArrayStack operateStack = new ArrayStack(10);
int num1, num2, operate, result;
int index = num1 = num2 = operate = result = 0;
char value;
while (true) {
value = expression.substring(index, index + 1).charAt(0);
if (operateStack.isOperate(value)) {
if (operateStack.isEmpty()) {
operateStack.push(value);
} else {
if (operateStack.priority(value) <= operateStack.priority(operateStack.peek())) {
num1 = numStack.pop();
num2 = numStack.pop();
operate = operateStack.pop();
result = operateStack.calculate(num1, num2, operate);
numStack.push(result);
operateStack.push(value);
} else {
operateStack.push(value);
}
}
} else {
String keepNum = "" + value;
if (index == expression.length() - 1) {
numStack.push(Integer.parseInt(keepNum));
break;
} else {
char nextNum = expression.substring(index + 1, index + 2).charAt(0);
if (operateStack.isOperate(nextNum)) {
numStack.push(Integer.parseInt(keepNum));
} else {
keepNum += nextNum;
numStack.push(Integer.valueOf(keepNum));
keepNum = "";
}
}
}
index++;
}
while (true) {
if (operateStack.isEmpty()) {
break;
}
num1 = numStack.pop();
num2 = numStack.pop();
operate = operateStack.pop();
result = operateStack.calculate(num1, num2, operate);
numStack.push(result);
}
System.out.printf("\n%s的结果是%d", expression, numStack.pop());
}
}
最新文章
- input文本框设置和移除默认值
- Greenplum：学习资料
- 一步一步配置NLB（续）之深入测试
- 【EasyUI】Combobox的联动和onChange/onSelect事件绑定
- hdu3037（lucas定理）
- SpringMVC全注解
- Canvas 数学、物理、动画学习笔记一
- 带你简单了解python协程和异步
- 20190329-盒尺寸、boder-
- 深入理解JVM（3）——垃圾收集策略详解
- spring boot 整合dubbo
- jquery鼠标放上去显示悬浮层即弹出定位的div层
- java后端实习生面试题目
- sql建立一种，自定义的执行作业
- 将win7电脑无线网变身WiFi热点，让手机、笔记本共享上网
- NAT—网络地址转换
- 修改查看MYSQL字符集（charset）
- 读到的"关于授权"
- ubuntu系统samba服务的安装配置
- caffe Python API 之激活函数ReLU