1.問題介紹
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsISM9AnYldnJwAzN9c3Pn5GcuQ0MlQ0MlcnW1JkbMp3aq1keBpnT5NGRNhHMT5keVRUT4FEROdXRE1UeZRUT3lERNlHMp10dBR1T1kFVNZXWE10dJRUT5hTaNdXQU9UNZRVT2NmMiNnSywEd5ITW110MaZHetlVdO1GT3lERNl3YXJGc5kHT20ESjBjUIF2Lc12bj5SYphXa5VWen5WY35iclN3Ztl2Lc9CX6MHc0RHaiojIsJye.png)
2.實作思路
3.代碼實作
第一個版本(采用這個)
public class ArrayStack
{
private int _maxSize;
private int[] _arr;
private int _top = -1;
/// <summary>
/// 初始化棧
/// </summary>
/// <param name="maxSize"></param>
public ArrayStack(int maxSize)
{
_maxSize = maxSize;
_arr = new int[_maxSize];
}
/// <summary>
/// 棧是否為空
/// </summary>
/// <returns></returns>
public bool IsEmpty() => _top == -1;
/// <summary>
/// 棧是否滿
/// </summary>
/// <returns></returns>
public bool IsFull() => _top == _maxSize-1;
/// <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 >= 0; 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 1;
}
else if (oper == '+' || oper == '-')
{
return 0;
}
else return -1;
}
/// <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 = 0;
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(10);
ArrayStack operStack = new ArrayStack(10);
//把字元串轉換成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 = 0;
int num1 = 0;
int num2 = 0;
int oper = 0;
string keepNum = "";
for (int i = 0; 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 + 1; 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());
}
}